Stack Overflow
Stack Overflow

Questions tagged [halting-problem]

The halting problem is a famous problem in theoretical computer science. Given as input a description of a program (typically a Turing machine) and an input to that program, the Halting problem is to decide whether that program terminates on that input.

The Halting Problem is a fundamental limitation on computability - that, given a program and a machine with infinite memory (usually a Turing Machine), it is impossible to know if the program will halt for a given input.

Although a program can be checked to see if it will halt on physical computers (because of limited memory), heuristics are used instead of an actual solution.

Here, most questions will have to do with how it impacts everyday coding and finding heuristics for code analysis purposes. However, consider asking your question on Computer Science if it is very abstract.

79 questions
83
votes
15 answers

Infinite loops in Java

Look at the following infinite while loop in Java. It causes a compile-time error for the statement below it. while(true) { System.out.println("inside while"); } System.out.println("while terminated"); //Unreachable statement -…
Lion
  • 18,729
  • 22
  • 80
  • 110
67
votes
13 answers

When have you come upon the halting problem in the field?

When have you ever personally come upon the halting problem in the field? This can be when a co-worker / boss suggested a solution which would violate the fundamental limits of computation, or when you realized yourself that a problem you were…
Claudiu
  • 224,032
  • 165
  • 485
  • 680
58
votes
24 answers

What exactly is the halting problem?

Whenever people ask about the halting problem as it pertains to programming, people respond with "If you just add one loop, you've got the halting program and therefore you can't automate task" Makes sense. If your program has an infinite loop, then…
poundifdef
  • 18,726
  • 23
  • 95
  • 134
56
votes
8 answers

Practical non-Turing-complete languages?

Nearly all programming languages used are Turing Complete, and while this affords the language to represent any computable algorithm, it also comes with its own set of problems. Seeing as all the algorithms I write are intended to halt, I would like…
Kyle Cronin
  • 77,653
  • 43
  • 148
  • 164
40
votes
4 answers

Determining whether a regex is a subset of another

I have a large collection of regular expression that when matched call a particular http handler. Some of the older regex's are unreachable (e.g. a.c* ⊃ abc*) and I'd like to prune them. Is there a library that given two regex's will tell me if the…
deft_code
  • 57,255
  • 29
  • 141
  • 224
30
votes
1 answer

Proof that the halting problem is NP-hard?

In this answer to a question about the definitions of NP, NP-hard, and NP-complete, Jason makes the claim that The halting problem is the classic NP-hard problem. This is the problem that given a program P and input I, will it halt? This is a…
templatetypedef
  • 362,284
  • 104
  • 897
  • 1,065
29
votes
24 answers

When is theoretical computer science useful?

In class, we learned about the halting problem, Turing machines, reductions, etc. A lot of classmates are saying these are all abstract and useless concepts, and there's no real point in knowing them (i.e., you can forget them once the course is…
Claudiu
  • 224,032
  • 165
  • 485
  • 680
25
votes
9 answers

Detecting infinite loop in brainfuck program

I have written a simple brainfuck interpreter in MATLAB script language. It is fed random bf programs to execute (as part of a genetic algorithm project). The problem I face is, the program turns out to have an infinite loop in a sizeable number of…
Sundar R
  • 13,776
  • 6
  • 49
  • 76
19
votes
2 answers

How does this proof, that the halting problem is undecidable, work?

I'm going over the proof for The Halting Problem in Intro to the Theory of Computation by Sipser and my main concern is about the proof below: If TM M doesn't know when it's looping (it can't accept or reject which is why a TM is Turing…
jfisk
  • 6,125
  • 20
  • 77
  • 113
15
votes
3 answers

Halting in non-Turing-complete languages

The halting problem cannot be solved for Turing complete languages and it can be solved trivially for some non-TC languages like regexes where it always halts. I was wondering if there are any languages that has both the ability to halt and not…
Shalmanese
  • 5,254
  • 10
  • 29
  • 41
14
votes
8 answers

Do all regular expressions halt?

Is there any regular expression that will, for some input string, search for a match forever?
Tom Lehman
  • 85,973
  • 71
  • 200
  • 272
10
votes
4 answers

"Finding all the code in a given binary is equivalent to the Halting problem." Really?

Was just reading the highly voted question regarding Emulators and the statement It's been proven that finding all the code in a given binary is equivalent to the Halting problem. Really stuck out at me. Surely that can't be true? Isn't it…
Maxim Gershkovich
  • 45,951
  • 44
  • 147
  • 243
8
votes
2 answers

Automatically and deterministicly testing a function for associativity, commutativity etc

Is it possible to construct a higher order function isAssociative that takes another function of two arguments and determines whether that function is associative? Similar question but for other properties such as commutativity as well. If this is…
TheIronKnuckle
  • 7,224
  • 4
  • 33
  • 56
8
votes
7 answers

Is there a "good enough" solution for the halting problem?

It is known that the halting problem cannot have a definite solution, one that a) returns true <==> the program does indeed halt, and b) handles any input, but I was wondering if there are good enough solutions to the problem, ones that can maybe…
EpsilonVector
  • 3,973
  • 7
  • 38
  • 62
7
votes
1 answer

Is mfix for Maybe impossible to be nontrivially total?

Since Nothing >>= f = Nothing for every f, the following trivial definition is suitable for mfix: mfix _ = Nothing But this has no practical use, so we have the following nontotal definition: mfix f = let a = f (unJust a) in a where unJust…
Dannyu NDos
  • 2,458
  • 13
  • 32
1
2 3 4 5 6