Talk:Halting problem

mini example for illustration

Would this kind of example be useful to show that it is really a non-trivial problem ? :

Input: natural number X > 0

function:
  while X > 1 loop
    If X is even then X := X / 2
    else X := X*3 + 1               (X is odd case)
  end loop

As far as I know this function always halts, but the proof is non-trivial (actually I do not know if such a proof exists :-)). lundril 194.25.174.98 (talk) 20:24, 17 January 2011 (UTC)

This is the classical Collatz conjecture. To my knowledge it remains unproven, i.e. there are no demonstrations that it is, or is not, an example of an undecidable question. So it probably is not suitable for inclusion into this article. To see how horrid it is, instead of multiplier m=3, use m=5 i.e. X := 5*X + 1. Then see what happens when you hit the "seed" X = 7. If this happens for multiplier m=5, why would we think we can prove that it will work for all X, given m=3? Possible O.R. alert: what happens when you conceive of this as a linear feedback system (in the engineering sense) with gain m = 3, 4, 5? Only gains less than 4 will result in convergence, stability, etc. BillWvbailey (talk) 22:37, 17 January 2011 (UTC)

Will, in the current context, I think you have to be extremely careful to distinguish the two meanings of undecidable. The Collatz conjecture is a single yes-or-no question, and is therefore definitely not undecidable in the sense the halting problem is undecidable, that is in the decision problem sense — you need infinitely many yes-or-no questions to be undecidable in that sense.

It could (in the sense that no one has yet refuted the possibility) be undecidable in the other sense, of being independent of some understood formal theory (which one? PA? ZF? something else?). However, if it's independent of any reasonable such theory, then it's necessarily true, because it's a Pi^0_1 assertion. (That is, if it were false, Peano arithmetic (say) would be able to prove that it's false, by exhibiting a counterexample. Since by hypothesis, PA can't do that, the conjecture must be true.)Struck out part was wrong — see below --Trovatore (talk) 02:32, 18 January 2011 (UTC)

Now, as to 194's question, yes, I suppose it's true that this example illustrates why it's a hard problem, in the sense that, if you thought that you ought to be able to just look at an arbitrary problem and figure out easily what it does and therefore whether it halts, you'd be wrong. Does anyone really think that? Surely no actual programmer thinks that :-). But it's not totally implausible on the face of it that some such example might be used to disabuse others of their illusions.

However Will Bailey's remarks illustrate why it's a bit of a risky thing to add; readers might easily become confused and think that, because we don't know how to decide some particular examples, that implies that there's no algorithm for the general case. The algorithm might incorporate insights that we haven't gotten around to. The undecidability proof shows that, no matter how insightful a programmer might be, the general case is simply impossible. --Trovatore (talk) 03:07, 18 January 2011 (UTC)

I should have looked a little closer at the example. My understanding of the classical conjecture asks For all x, does the m=3, c=1 version of the algorithm terminate at 1? This is doubly difficult, because it involves two unbounded counters.

I thought the decidability question comes (at least in part) from the structure of the algorithm, i.e. whether or not the algorithm includes an unbounded mu-operator, i.e. a "for all" construction followed by "there exists" construction. Here our inner loop is a predicate asking the question: For a given seed x, does there exist a number f when this algorithm terminates at 1? If we equip our inner loop with an inner_loop_counter, we will necessarily have a number f that we can associate with this individual question: (Ex)R(a,x) = (Ex)T(f,a,x). (Kleene 1967:269). But can we do this? No. For a given seed the only way to determine f would be for inner_loop to terminate at 1, but there may be a seed such that this algorithm can go on ad nauseum, incrementing inner_loop forever (as shown in the 5*x + 1 example). The only way to escape this situation is via a number MAX set on the number of inner loop iterations and then an if-then to compare "inner_loop_counter" to MAX. But we don't know how big to make MAX!

Then the general problem of "for all integers" just compounds the misery (pardon my pidgin programming, I'm an assembly-language guy). The question I'm asking is: will this algorithm HALT? (when we find a seed that doesn't result in descent to 1). Or is the question (potentially) undecidable, i.e. there exists no possibility of even hoping to answer it one way or the other--

function:
  seed := 1
  MAX := ?? (a really big number? But ''how'' big?)
  outer_loop:
      inner_loop_counter := 0 
      X := seed
          inner_loop: while X > 1 loop
            If X is even then X := X / 2
            else X := (X*3 + 1)/2               
               If inner_loop_counter > MAX then HALT
               else inner_loop_counter := inner_loop_counter + 1
          end inner_loop
      seed := seed + 1
      inner_loop_counter := 0
  end outer_loop

For example the 5*x + 1 version loops forever at seed = 5 and explodes (I think, but who knows?) at seed = 7. Just based on the structure of the algorithm alone, can we ask the simple question: For a given m and c, will this algorithm be undecidable? Am confused. Thanks, BillWvbailey (talk) 17:38, 18 January 2011 (UTC)

What do you mean "will this algorithm be undecidable"? What's an undecidable algorithm? --Trovatore (talk) 20:30, 18 January 2011 (UTC)

Is the matter formally undecidable whether or not this algorithm will halt? If it is then there's no point in pursuing the Collatz conjecture further, right? BillWvbailey (talk) 21:15, 18 January 2011 (UTC)

How are you using the word undecidable here? Do you mean in the decision-problem sense, in the sense of being independent of some understood formal theory (which one?), or some third thing? --Trovatore (talk) 21:32, 18 January 2011 (UTC)

I just want a proof, if such a thing is possible, of whether this particular algorithm will HALT or not (assume the ideal case where it's been programmed into a counter (abacus, Lambek) machine). The answer I'm after is not whether or not it will halt (we know that one of these is the case, we just don't know which one). The answer I'm looking for is: which one? Can we determine which case it will be for this particular algorithm or not: if so, why, and if not, why? BillWvbailey (talk) 22:00, 18 January 2011 (UTC)

Do you mean a proof in a particular formal theory? Or are you asking whether the answer (to whether the program will halt) is knowable at all? --Trovatore (talk) 22:24, 18 January 2011 (UTC)

Both. Ultimately it's the later which is the most interesting: a priori (in any theory) before running this algorithm, can we know if it halts? Or, let's restrict ourselves to (whole-, or integer-) number theory, can we know if it halts? I think, though, I'm beginning to see your point. . .

RE other theories: Per the O.R. alert above, if we use a different theory (linear systems theory) we get the sense that only for m<4 will the conjecture be true. In cases of m > = 4 it will fail. But the spirit of the conjecture is (whole-, or integer-) number theory. Bill Wvbailey (talk) 22:46, 18 January 2011 (UTC)

So I don't actually know the answer to the question in either form; I was mostly trying to make sure you understood that they are two very distinct questions.

The question of whether first-order Peano arithmetic (say) fails to decide whether one of these algorithms halts, is one for which we have techniques that could potentially settle the issue. I don't believe anyone has shown that PA fails to decide it. Note however that (i) if PA fails to decide the question, for one of these algorithms, then that algorithm does not in fact halt, and therefore (ii) any way in which we could come to know that PA fails to decide the question, is also a way in which we would come to know that the algorithm does not halt.

Now, on the other question, the "absolute undecidability" one, we have no technology whatsoever that could address that (except by refuting it). It is difficult to imagine what such a technology could look like. The only reason we can prove independence results, namely that a given formal theory fails to decide something, is that we have a complete description of what it means for the formal theory to decide something. We have no similar demarcation of what it means for us to come to know something in any way at all. --Trovatore (talk) 22:53, 18 January 2011 (UTC)

Oops — I was careless in the struck-out parts above. The conjecture is actually not (in any obvious way) Pi^0_1. It's Pi^0_2. So the claims about it being true if independent do not follow, at least in any obvious way. --Trovatore (talk) 09:54, 19 January 2011 (UTC)

That was interesting. You forced me to be precise in my thinking. I learned something. Wouldn't you love to nail this Collatz Conjecture using, say, Peano/discrete arithmetic and put an end to further consideration of it (with regards to discrete mathematics)? [I hope I wrote that correctly . . . in other words, pick away at it slowly, using theory after theory]. Thanks, Bill Wvbailey (talk) 23:38, 18 January 2011 (UTC)

PSPACE

What's with the note about PSPACE being added? The Halting problem is polynomially 1-complete: any computable problem reduces to it with a polynomial-time one-one reduction. There's nothing special about PSPACE compared to P, EXP, NP, etc. — Carl (CBM · talk) 11:37, 1 March 2011 (UTC)

Rice's Theorem and Halting Theorem

I feel a bit sheepish about undoing a good faith revision by an expert contributor with a strong record, but I feel strongly that simply eliminating this paragraph weakens the article. And they do say, "Be Bold!"

Rice's Theorem bridges the Halting Theorem into vast areas of everday Comp. Sci. practice. Without a reference to it, the implications of the Halting Problem can seem must more limited than they are.

It is possible to criticize the terminology, which certainly would not pass muster for a refereed journal. The terms "function" and "algorithm" are used where the precise term would be "partial function". The trouble is the non-mathematical reader won't know what a "partial function" is. If this is an issue, revision is the answer, not deletion.

I don't know which semantics of the term "consequence" Rice's Theorem fails with reference to the Halting Problem. Rice's depends directly on the Halting Theorem. In terms of train of thought and history, Rice's Proof more directly derives from the Halting Theorem than from any other result.

I think Rice's has a history of being underappreciated. I know that when I got my MSCS it was not even mentioned in the Theory Course. Every working programmer should know what the Halting Problem is, and why it is significant, and every working programmer should know what Rice's Theorem is, and why it is significant.

--Jeffreykegler (talk) 01:04, 8 May 2011 (UTC)

I changed the paragraph to say Rice's theorem generalizes the theorem of the unsolvability of the halting problem. I think that is easier to agree with. — Carl (CBM · talk) 10:43, 8 May 2011 (UTC)

I've tightened the language in the Rice's Theorem section, while still trying to keep it comprehensible to the non-specialist. I changed "algorithm" to "program" and "function" to "partial function". I briefly explain what a partial function is. Also, instead of saying that an algorithm defines a function, it nows says that a program implements a partial function. --Jeffreykegler (talk) 15:27, 8 May 2011 (UTC)

Usually you say that theorem B is a consequence of theorem A if the dictum of B follows by a relatively easy proof from the dictum of A. If A is "halting is undecidable" and B is "X is undecidable" for some free property X, is there an easy proof from A to B? I don't think so.

The paragraph was improved by Carl's edit (and further clarified by your later edits), but is still open to a serious misunderstanding. Take a program implementing the identity function. We know that the partial function implemented by that program has the non-trivial property that on input 0 it will halt with output 0. But the current text could be interpreted by the unsuspecting reader to imply that it is undecidable whether this program will halt on input 0. There are several quantifications over bound variables that play quite different roles, but the text does not elucidate that difference. First there is the non-trivial property over the domain of partial functions; let's use the letter P. Then there is (the Gödel number of) the program; let's use an N. The function implemented by N is Φ_N. Then the theorem states that for all non-trivial P, there is no algorithm A such that for all N we have Φ_A(N) = P(Φ_N). That the quantifiers have this order, ∀P ∄A ∀N, is not clear from the present text.  --Lambiam 22:04, 13 May 2011 (UTC)

Request to include a "reductio" proof together with the diagonalization proof

I've wondered about this myself, and think this will be an interesting discussion. I won't easily be convinced that they're the same. If they're equivalent they are reducible to one another, but I'd like to see the evidence. Bill Wvbailey (talk) 22:41, 4 November 2011 (UTC)

The following is from the archives (2006). No one commented on these drawings, or their inclusion:

From Minsky (1967)

The above and following are derived from Minsky's proof (1967) but it is similar to the one on the article page. Some readers may find this easier to follow -- there does seem to be a lot of fiddling with the page example. If anyone thinks such a drawing is a good thing and would want me to modify or otherwise can suggest improvements lemme know and I can rework it, split it into pieces (see example below) so they're easier to see, whatever. If anyone is worried about copyright issues -- I did not cc exactly, and attribution to Minsky should be provided. If all think its a bad idea or a waste of time, lemme know and I'll just leave it here; this is easy to do once you get the hang of it. Click on the images to see better. wvbaileyWvbailey 16:13, 30 June 2006 (UTC)

Also, I found a virtually-identical version to Minsky (1967) -- but words only, no drawings -- on pages 171-172 in Edward Beltrami, What is Random: Chance and Order in Mathematics and Life, Springer-Verlag, NY, 1999. wvbaileyWvbailey 17:11, 30 June 2006 (UTC)

From Minsky (1967)

Bill Wvbailey (talk) 23:41, 4 November 2011 (UTC)

The proof in the article starts with an arbitrary total computable function, and proves it does not compute the halting problem. To make it a reductio proof, at the top replace

To this end, given any total computable binary function f,

with

To this end, given any total computable binary function f, and assume f equals h

Then, at the bottom, replace

In either case, f cannot be the same function as h. Because f was an arbitrary total computable function with two arguments, all such functions must differ from h.

with

In either case, f cannot be the same function as h. This is a contradiction, because we assumed f equals h. Thus h cannot be computable.

As you can see there is no actual change to the meat of the proof; the "reductio" wrapping just serves to make an extra assumption (the f equals h) that is never used in the proof, only so that at the end the proof writer can say "contradiction!". It does not make the proof easier. — Carl (CBM · talk) 02:31, 5 November 2011 (UTC)

-- My reading of the editor's intent is that he/she is trying to present a simplified version that avoids diagonalization. I agree that turning the existing proof into a reductio wouldn't be an improvement. But the one that Minsky presents skips any mention of diagonalization, and resorts to a trick -- grafting a tiny state machine onto/into the main TM so that, when it tries to decide about itself, causes the whole assemblage to oscillate in a sorities no matter what outcome of the decision. I guess the question is: is the Minsky proof just a sheep in wolf's clothing, or is it a fundamentally-different proof? Martin Davis also presented a version in which diagonalization is never mentioned. I'm always drawn back to Turing's original proof that uses a TM to march through the numbers until it arrives at its own (clearly a diagonalization), at which point it then it falls into a sorities, a neverenging callup of itself. The interesting thing about these constructions is what happens when they arrive at their own number; really, there's no need to invoke a diagonalization "all the way up from 0" because the problem always appears at machine's own number. The question is: are there any proofs out there that don't invoke diagonalization, don't require it? Or is diagonalization embedded in all of them, some just more tacitly than others? Bill Wvbailey (talk) 15:28, 5 November 2011 (UTC)

One simple path is to prove (without diagonalization) that the Busy Beaver function S is not computable, but that it would be computable if the Halting Problem were solvable. Possibly this approach has already been discussed here?
— r.e.s. (talk) 01:16, 6 November 2011 (UTC) Edit: See this discussion section. (Hmmm ... I see that someone objects that this method does use diagonalization.) — r.e.s. (talk) 01:22, 6 November 2011 (UTC)

Gaffe: diagonalization process is a total function not computable?

David Eppstein reverted my footnote, which I trimmed to just the Penrose reference, but I'm trying to figure out where I've gone wrong. I see a clue (that I'm having a hard time accepting without proof) in the footnote in Rogers 1987:10, g and h here are the diagnonal entry, and h(x) is the g_x(x)+1:

"The proofs that g and h are primitive recursive use the logical principle of the excluded middle. Such nonconstructive methods are qualified or rejected in various "constructive" reformulations of mathematics, such as that of the intuitionists. [etc]

The problem I'm having with this is that the diagonalization process itself, i.e. g_x(x) over the infinite (i.e. the numbers-as-index) never terminates. How could it unless you accept a transfinite notion of "terminating". So how do we convince ourselves that it constitutes a total "function"? I thought a total function has to terminate for all values plugged into it; it's a function first, meaning that it terminates, and total (meaning it's a function over its defined inputs) second. It would seem that any algorithm that performed diagonalization over the primitive-recursive functions would seem to require a mu-operator in it to "keep it going" down the diagonal ad infinitum, and that makes it non-primitive-recursive.

I find this in Kleene 1952 re Partial Recursive Functions:

The exploration of various methods which might be expected to lead to a function outside the class of the general recursive functions has in every case shown either that the method does not actually lead outside or that the new function obtained cannot be considered as effectively defined, i.e. its definition provides no effective process of calculation. In particular, the latter is the case for the Cantor diagonal argument."

I read this as Kleene saying that the "Cantor diagonal argument" is ineffective, i.e. it's not a function, so how can it be "total"? Are there constructive proofs that diagonalization is "total"? Or am I so far gone into the land of the confused that I cannot be saved. Thanks, Bill

You seem to be confusing a function (a mathematical object that relates a single value to each argument) with an algorithm (a process defined by a discrete set of computational steps, that always terminates). The result of an algorithm is a function, but not every function comes from an algorithm. This distinction is central to the whole point of this article. —David Eppstein (talk) 20:16, 12 December 2011 (UTC)

RE your response, I've got a couple questions, my research isn't helping me (this isn't off-topic, it's also connected with the question in the section above, about alternate forms of Halting-problem proof):

• For every point on the continuum, is there a function that defines it? If Anglin is correct that "real numbers can be defined in terms of rationals, rationals in terms of natural numbers, and natural numbers in terms of sets" (Anglin 1994:217) then this seems to imply that a number-theoretic (i.e. computational) method (to distinguish it from an algorithm that terminates) can be attached to every real number.
• What is the "nature" of diagonalization itself? Is it a "function"? Is it a computational method? I can see in a finite version, such as the examples on the Cantor's diagonal argument page, it is clearly algorithmic -- computational and terminating e.g. other words it spits out the "anti-diagonal from three input "vectors"( 1, 0, 1), (1, 0, 0), (0, 1, 0) ==> (d1, d2, d3) =( 1, 0, 0), use an algebraic version of NOT d1, NOT d2, NOT d3 on each element to get a "vector" outside the three I started with ( 1-1, 1-0, 1-0) = ( 0, 1, 1). But when applied to an infinite input what is it (function? method? none of the above)?

Can you point me to some reading that might help? Thanks, Bill Wvbailey (talk) 17:22, 13 December 2011 (UTC)

I don't think I really understand what this discussion is about. Bill, are you just asking whether excluded middle is needed to prove the existence of a total nonrecursive function, in the sense that, say, Heyting arithmetic does not prove that? I'm not an expert on that sort of question, but I think that is indeed true. What is the actual dispute about? --Trovatore (talk) 18:53, 13 December 2011 (UTC)

It's not a dispute. It's my confusion about diagonalization and its use. Here's how it started: I asked someone to review some wording in a footnote I wrote. David reverted it. That's okay, no problems there. But I thought I understood what I wrote. So the issue is my confusion, and probably most everyone who tries to understand exactly what sort of thing (computational procedure?) the diagonal method really is, and how it can be used:

I wrote:

"See also Rogers 1987:9-11 for a discussion of how diagonalization -- a constructive, algorithmic process -- creates functions that "fall outside" the class of every total (e.g. primitive-recursive) function. Diagonalization can also be applied to the partially recursive functions, i.e. those that don't terminate for some input values, such as a poorly-designed division program. Because these are still algorithmic, they too can be enumerated."

In his reversion note David wrote:

"Functions created by diagonalization are total. They are just not computable."

I'm re-reading the pages where Rogers is demonstrating how to "diagonalize out of" the primitive recursive functions [prfs] (pages 10-11). Part of my gaffe that confused you (asking the non-constructive proof question, sorry 'bout that) is that the footnote at the bottom of the page of 10 is actually associated with the discussion on page 9 about the Goldbach conjecture.

That's my bad. My problem now is I'm not having much luck convincing myself that Rogers' construction, clearly intended to go on forever, should be allowed to construct a non-prf function, it's like assuming what you're trying to prove: "Here's a non-prf function-like process that I'm going to now use to produce a non-prf [process? function?]".

Rogers' "process" enumerates the primitive recursive functions of one variable, then sticks the functions' indices x into the functions to create h(x) = g_x(x)+1. This creates a contradiction, implying h is not primitive recursive. Even if I did understand the contradiction (I'm working on this) why should Rogers permit himself use of a non-terminating method to "diagonalize out" of the primitive recursive functions. I had thought, at least until now, that all primitive recursive functions are total and therefore terminate for all their values. And David's response that the diagonal method creates total functions that are not computable, adds to my confusion. Clearly I'm missing something, something probably obvious, I just haven't figured it out yet. Bill Wvbailey (talk) 18:52, 14 December 2011 (UTC)

That construction - diagonalizing against an enumeration of all primitive recursive functions - makes a function that is computable but not primitive recursive. If you diagonalize against an enumeration of all the total computable functions, the resulting function will be total and not computable. This is one way to prove that there can be no computable enumeration of all total computable functions. — Carl (CBM · talk) 19:21, 14 December 2011 (UTC)

Last questions: Now that I understand the primitive-recursive diagonalization proof, what you and David wrote seems very subtle and counter-intuitive indeed: "If you diagonalize against an enumeration of all the total computable functions, the resulting function will be total and not computable". Is this, in essence, what is behind Rogers' Theorem VIII (p. 26)? If not can you direct me to a proof of what you wrote? By the way, thank you all (David and Trovatore and Carl) for your help. Bill Wvbailey (talk) 21:15, 15 December 2011 (UTC)

---

If by "For every point on the continuum, is there a function that defines it?" you mean something like "is there a function f(i) that equals the ith digit of the given number?" then the answer is yes. If you mean "is there a computational procedure that returns the ith digit?" then the answer is no. For an example of a number whose digits cannot all be computed, see Chaitin's constant. —David Eppstein (talk) 19:31, 13 December 2011 (UTC)

Total state edit

Arthur, I reviewed the quote from Minsky (which I found for Carl, he inserted it way back when) and it's okay (page 25 in Minsky 1967). Here's the problem: unless we make it very clear that the "state of the computation" is not the contents of just the FSM's state register, but of the total state of the TOTAL machine that includes ALL the memory involved (e.g. the FSM state register + tape squares used + data + "scratchpad memory"), then the reader will be confused. I can back this up with quotes from Kleene 1952 and Turing 1937, plus my own experiences and probably Davis if I were to hunt for it. Thus, for example a Post-Turing machine, operating a "universal program", will contain around 256 instructions (2^8 for the FSM's state register; been there, wrote it). But the simplest multiplication program will contain about 160 "bits" (plus or minus, about 20 isnstruction x 8 bits per instruction) in the executable program on the tape (been there, wrote that too), not counting the two numbers to multipy. So the total number of states involved here is roughly 2^(8+160 plus or minus), i.e. 2^168 states. We have to count the executable code, because it requires marker/pointer bits throughout, and the jump-instructions require either changes of bits or a "counter" scratch-pad that comes and goes. So the total bit-count is more than 168+/-. Very difficult to estimate.] This all is very technical, so it would be better to revert the edit previous to mine rather than leave this point not go clarified. Thoughts? Bill Wvbailey (talk) 04:10, 30 January 2012 (UTC)

I think that all that we need is that the number of possible states (on a specific bounded tape) is finite; the exact calculation doesn't seem to add anything. I'll have to look over the edits to see which version best encapsulates the finiteness (finitarity? whatever) without going into details. — Arthur Rubin (talk) 07:05, 30 January 2012 (UTC)

I agree with your point and your edits. Bill Wvbailey (talk) 16:24, 30 January 2012 (UTC)