Talk:Halting problem/Archive 5

Archive 1

←

Archive 3

Archive 4

Archive 5

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)

Did Turing prove the undecidablity of the halting problem?

The introduction now says

1. '[T]he halting problem can be stated as follows: "Given a description of an arbitrary computer program, decide whether the program finishes running or continues to run forever". This is equivalent to the problem of deciding, given a program and an input, whether the program will eventually halt when run with that input, or will run forever.'
2. 'Alan Turing proved in 1936 that a general algorithm to solve the halting problem for all possible program-input pairs cannot exist.'
3. 'It is often said that Turing stated and proved the halting theorem [...], but strictly this is not true' (quoting Copeland). (I assume 'the halting theorem' refers to the undecidability of the halting problem.)

Is there a way to make it clearer how all three of these can be true? I'm certainly missing how the first two statements don't imply that Turing showed the halting problem undecidable. Theodore.norvell (talk) 01:42, 7 September 2012 (UTC)

The last part of the lede was supposed to be a footnote giving an explanation of the last sentence. All that (3) is trying to say is that Turing did not literally use the term "halting problem", which was coined by Davis. Turing did prove what we would now call the unsolvability of the halting problem, but he didn't use the modern terminology. I moved the tangential explanation back to a footnote where it was intended to reside. — Carl (CBM · talk) 02:43, 7 September 2012 (UTC)

Thanks. That makes more sense. Perhaps the problem also lies a bit in the wording of point 2. In his 1936 paper, Turing showed that no Turing machine can determine whether or not an input Turing machine is circle-free. Circle-free means roughly, but not exactly the same as, "always halts on an empty tape." So there are two differences, both minor. First, Turing didn't (as far as I can tell) write about the arbitrary input case. Second, a halting TM is a bit different from a circle-free TM. These differences might account for Copeland's statement. Theodore.norvell (talk) 10:35, 7 September 2012 (UTC)

---

The details of this can be found in the archive 2006, including Davis's response to my question that I emailed him. The folliwng is from that archive:

"Origin of Halting Problem?: a proof by S. C. Kleene (1952) and so named by Martin Davis"

As I noted above, Martin Davis said in his e-mail to me that he coined the name "halting problem" but he added that in fact the first expression of the notion of an algorithm that could detect if a machine would stop was on p. 382 of S.C, Kleene's book of 1952, first paragraph "buried half way down":

S. C. Kleene, Introduction to Metamathematics, North-Holland Publishing Company, Amsterdam NY, first published 1952, Tenth impression 1991.

As this book may be hard to find I will quote the entire paragraph:

The proof appears in immediately after § 70 Turing's Thesis:

§ 71 The word problem for semigroups "Church's original example of a decision problem which, on the basis of his thesis, is unsolvable was constructed in therms of λ-definability (1936). The corresponding example given above (Theorem XII §60) is constructed in terms of general recursivenss (following Kleene 1936, 1943). Turing 1936-37 gave examples constructed in terms of computability. This can be done e.g. as follows. A machine M is determined by its table, containing (j+1)k entries. We can set up a Gödel numbering of the tables, and thus of the machines. Then the function ξ defined as follows is not computable: ξ(x) = 0, if x is the Gōdel number of a machine Mx, and the partial function φ(x) of one variable which Mx computes has 1 as value for x as argument and ξ(x) = 1 otherwise. So by Turing's thesis (or via the equivalence of general recursivenss and computability by Church's thesis) there is no algorithm for deciding whether any given number x is the Gōdel number of a machine which, when started scanning x in standard position with the tape elsewhere blank, eventually stops scanning x, 1 in standard position. As another example there is no algorithm for deciding whether any given machine, when started from any given initial situation, eventually stops. [boldface added] For if there were, then, given any number x, we could first decide whether x is the Gödel number of a machine Mx, and if so whether Mx started scanning x in standard position with the tape elsewhere blank eventaully stops, and if so finally whether x, 1 is scanned in standard postion in the terminal situation." (p. 382, Computable Functions, CH. XIII)

Eventually an editor found the footnote in Copeland that verified all of this. Hope this helps. BillWvbailey (talk) 20:06, 7 September 2012 (UTC)

Python is psudeo code?

In the first section w/ "Pseudo code", it is actually a valid statement in python 2 and runs as intended. Is it really Pseudo Code? — Preceding unsigned comment added by TheKing44 (talk • contribs) 22:49, 12 December 2012 (UTC)

The proof is invalid

The proof is invalid because g is not computable. Instead it would be stuck in infinite recursion that inhibit it's proposed function. The two parts of g are not separable, but rather interact in a way that dictates computability apart from the computability of each separate part. — Preceding unsigned comment added by 24.98.49.192 (talk) 18:50, 21 August 2012 (UTC)

g is (partial) computable if f is total and computable. As f was supposed to be computable and equal to h, that was true by assumption. — Arthur Rubin (talk) 20:13, 21 August 2012 (UTC)

The way I eventually worded the matter to myself is: "$e(e)$ is a program that halts when and because it doesn't halt, and it doesn't halt when and because it halts (given $f=h$). Such program is impossible, therefore a program for $h$ is impossible, either". Are there statements of this kind in literature? I'm sure they'd make understanding much more easy. 89.110.5.231 (talk) 20:00, 6 April 2013 (UTC)

There are proofs such as this one: http://www.comp.nus.edu.sg/~cs5234/FAQ/halt.html 217.155.35.160 (talk) 02:08, 20 May 2013 (UTC)

The proof is invalid for a different reason than what is stated here. If you modify g to be that g(i) returns 1 when f(i,i) is 1 and is undefined otherwise, then h(i) very well can be the same as f(i,i), which (may I remind you) is also a binary function. The resulting psuedocode would read --- procedure compute_g(i):

  if f(i,i) == 1
     return 1
  else
     loop forever

--- The computation of g shows that there are exactly two result cases:

1. g(i) = f(i,i) = 1. In this case, h(i) = 1 because g(i) halts on input i.
2. g(i) is undefined and f(i,i) = 0. In this case, h(i) = 0 because g(i) does not halt on input i.

Another thing to note is that in the original proof, if you instead define a function d(i) that returns 1 if a program loops forever and 0 otherwise, h(i) = ~d(i). Is there another proof that takes a different direction from this? Are there details missing from the original source? Or have I broken a century-old paradox? :) Compynerd255 (talk) 15:11, 15 May 2013 (UTC)

The proof shows that f cannot be the same function as h by showing that there's an e such that f(e, e) ≠ h(e, e). An example where f(i, i) = h(i, i) wouldn't contradict this. 217.155.35.160 (talk) 02:08, 20 May 2013 (UTC)

Whoops, I just read the proof again and realized that it was talking about a program e that computes g, creating a paradox. Sorry about that. It would be nice if the fact that h is being run on e is clearer. — Preceding unsigned comment added by Compynerd255 (talk • contribs) 19:45, 21 May 2013 (UTC)

Relevance?

the article describes the concept but fails to describe why the topic is relevant or significant. Significance is an important test of whether an article belongs in Wikipedia. Stephen Charles Thompson (talk) 02:14, 29 December 2012 (UTC)

The halting problem obviously satisfies the general notability criterion, which is the low bar for whether an article belongs in Wikipedia. If you don't think the article sufficiently makes the case that the topic is signifiant, you are free to modify the introduction. —Mark Dominus (talk) 04:03, 29 December 2012 (UTC)

Equivalence to verifying a mathematical proof

It appears to me that verifying a mathematical proof may be isomorphic to following a program - instead of following predetermined instructions that are defined to the CPU and stopping when you get to an instruction that terminates the program, you evaluate the statements and follow where it follows to continue next and stop when you get to QED. And if they are not isomorphic because "evaluating a statement" and "following an instruction" may not be equivalent, that verifying the proof can only be the harder of the 2 problems as a result.

I have also heard some people claim that if P=NP that a mathematical proof generating program could be made. This is because they make a tacit assumption that verifying a mathematical proof is a polynomial time process, but I believe that they merely have a bias for making this conclusion because they have personal experience writing proofs and personal experience reading proofs and know that reading them is much, much easier. But that doesn't make the one that seems to be easier necessarily polynomial time, or even decidable, just that the proofs that they have experience with have been seemed to them to be easier to read than to write. The way I see it, at the absolute least, it is not only not polynomial-time to verify a mathematical proof, but doing so is AS hard as the halting problem, that it may only in fact be a harder problem, because what exactly is involved in evaluating a statement in the proof is not completely clear, whereas following instructions that necessarily adhere to a CPU's predefined set of instructions can only be easier than that. And yet the halting program itself is undecidable, and so verifying a proof must be undecidable; you cannot make a program that verifies an arbitrary proof that proves something over an arbitrary set of inputs any more than you can make a program that determines if an arbitrary program will halt on all inputs. Thus even if the P vs. NP problem was resolved in favor of P=NP with a tangible algorithm that does it, that still wouldn't allow for proof-making programs that work in polynomial time for any arbitrary thing since the people who have stated this have simply assumed that verifying a proof is polynomial time, while if I am right, it is the greatest possible oversight to declare something that is undecidable as something that can be decided in polynomial time. And so the undecidability of the halting problem implies that the P vs. NP problem isn't as important as many people attribute it to being; it wouldn't allow for revolutions in artificial intelligence. Only problems for which verification of a solution to that problem is polynomial time could in principle be solved in polynomial time, and the problem of proving theorems of mathematics is not such a problem.

207.225.95.253 (talk) 15:28, 31 December 2012 (UTC)

Hi, 207.225.95.253. This is a talk page for a Wikipedia article, and its purpose is to discuss what, if any, changes to the article would improve the article. It is not for general discussion of the subject matter. I would be happy to copy your text to Wikipedia:Reference desk/Mathematics for you, except that it ought to be phrased as a question, and I think you should probably do the rephrasing. --Trovatore (talk) 18:25, 31 December 2012 (UTC)

For what it's worth, I think the IP has a point in regard verification of a proof — but on P = NP, rather than this article. An annotated proof system can be verified easily, but I can imagine a raw proof (collection of statements) might require some analysis, and might be an NP process which could conceivably be NP-complete. It would still require a source, but it would be of interest. — Arthur Rubin (talk) 18:57, 31 December 2012 (UTC)

More recent developments

I am by no means an expert at this, but I stumbled upon an article by computational scientist Christian S. Calude titled "Most programs stop quicly or never halt". This article (among others) explores halting probabilities. — Preceding unsigned comment added by 84.215.248.204 (talk) 15:42, 1 May 2013 (UTC)

Human brain (why does the article mention it?)

I'm not sure what a human brain has to do with this. The article talks of machines that can run algorithms, but our brains are not intended for running algorithms, right? In the sense that the steps of our problem solving are not once established and predefined — we can never precisely know what we do next! We never quite faithfully obey the strict logic that makes part of any algorithm, we do it differently, by other means, without establishing absolute truths... For example, one cannot make a human brain loop forever, therefore, the idea of proof that was presented in the article does not apply to us at all. I think, the matter really needs clarifying (if there is a link, then what is that link?). - 92.100.173.55 (talk) 12:44, 7 April 2013 (UTC)

Copeland 2004 seems to speculate on whether a human being (mind, brain) can solve the halting problem. I don't know if the reference to brain is helpful, but that sentence seems generally appropriate and adequately sourced. — Arthur Rubin (talk) 16:17, 7 April 2013 (UTC)

Well, what puzzled me is that the reference to the 'unknown physical processes that could solve the halting problem for a Turing machine' looks somewhat mysterious (while surely not inappropriate if sourced). I guess Copeland has presented some good argumentation that they might play substantial role inside our brains (otherwise it is not a very good thing to just assume that our brain employs different physics than the rest of the world). Such argumentation would be not obvious, at least... - 92.100.173.55 (talk) 17:51, 7 April 2013 (UTC)

According to Godel Escher Bach, our human brains do follow a strict logic as found in the structures of our neurons - they fire deterministically if the sum of the inputs being fired to them is above a certain threshold. If this is perfectly true, then human brains are Turing machines and thus cannot solve the halting problem (we sure try, but we tend to overlook details and get it wrong). The algorithms in our systems are built towards solving a problem quickly with reasonable accuracy. And, in a sense, since there are many thoughts running in the brain at once, individual thoughts can go in an infinite loop - they're just killed by the parts of our brains that detect futility. Compynerd255 (talk) 15:11, 15 May 2013 (UTC)

That is, one single algorithm for living, and no special algorithms for specific tasks. Cool... Still, if we're not machines that can run various precise algorithms, and if the article deals with such machines only, then the article isn't supposed to talk of us, strictly speaking... On the other hand, well, it doesn't talk of us very much. :) - 89.110.31.147 (talk) 03:31, 24 May 2013 (UTC)

In other words, from "our neurons work deterministically" it does not follow that our brains are akin to Turing machines. The car engine works deterministically (one could say, it employs an algorithm), but it is not akin to a Turing machine because it cannot run algorithms different from its own. Now, the question is, what means the expression 'halting problem' in application to human brains that don't seem to behave like Turing machines. - 89.110.28.61 (talk) 23:21, 24 May 2013 (UTC)

The point of all of this is that there is no magical problem solving ability that humans have to solve undecidable problems better than computers. Most of the comments alleging otherwise (e.g. the one immediately above about brains not behaving like Turing machines) seem to be more wishful thinking than based on actual physics. The relevant link here is Church–Turing thesis, according to which nothing in the universe (including human brains) cannot be accurately simulated by computers. —David Eppstein (talk) 01:50, 25 May 2013 (UTC)

There were no comments alleging otherwise, and the one you're referring to is not an example of such comment. Instead, it meant to say that the halting problem is not applicable to human brains, with all their physics. And I see no way in which the Church-Turing thesis is relevant here. We can simulate many physical things with computers, but those things don't become like computers after that, nor do brains as we see.

There is no problem that we can decide with certainty, and the only way to get absolute certainty for conclusions on whatever problem solving is to build algorithmic machines; naturally, the properties of such machines are not like the properties of our brains. So, what brains might have to do with the subject of the article? - 89.110.28.61 (talk) 02:14, 25 May 2013 (UTC)

OK. I just don't understand why the materialist model of mind should have many things to do with Turing machines or Turing equivalence. It certainly should incorporate a model for knowledge representation, together with deterministic means for updating such model, but its ways of deriving knowledge should be guesses more often than any kind of strict reasoning, and the guesses should be selected for their verosimility, that is, being similar to some things that are already known to be verosimilar. The Turing machine does not seem to process data in such a way – instead, it is aimed at guaranteed problem solving, which is a different kind of knowledge. The Turing machine should surely be able to model human means of knowledge processing, but this does not mean that it models itself in doing so – in the same way, it does not model itself when it models a car. - 89.110.3.6 (talk) 10:52, 3 June 2013 (UTC)

Maybe the confusion here is because in the halting problem, the Turing machine appears twice, once as the machine solving the problem and secondly in a different way as the machine whose halting is to be tested. Do human brains halt reliably after given some inputs and not after others, and does the halting problem model that behavior? No, that's silly. Does the undecidability of the halting problem imply that it is impossible for human brains to reliably and accurately solve all halting problem instances? YES. Or more precisely, whatever formal reasoning system you use (such as the axioms of ZFC set theory), there will exist instances that have no proof in that system, regardless of whether you use a computer or a brain to search for the proof. —David Eppstein (talk) 15:35, 3 June 2013 (UTC)

NP-hardness

The article does not mention that the complexity of the halting problem on finite state machines is in NP-hard. — Preceding unsigned comment added by 91.19.101.37 (talk) 13:15, 5 August 2013 (UTC)

Why is that an interesting phenomenon? Isn't it also $\Pi _{2}^{P}$-hard? — Arthur Rubin (talk) 15:26, 5 August 2013 (UTC)

xkcd 9/18/2013

Today's xkcd takes up the halting problem. Daniel Case (talk) 16:50, 18 September 2013 (UTC)

Two concerns

• What is [[c2:HaltingProblem]]? I can't find what it expands to, and why it should be here.
• What is the purpose of the (unsourced) section "Avoiding the halting problem"?

— Arthur Rubin (talk) 20:07, 14 January 2014 (UTC)

I have no idea about the c2 link. It looks safely removable. As for avoiding, there are two reasons for being interested in the halting problem: (1) mathematically, it gives a nice example of an undecidable problem, and (2) in practical computer programming, it is generally important to be able to tell that your program has no infinite loops, but the halting problem says you can't always do that. This section appears to be about ways of solving the practical problem and guaranteeing that your program will always halt. But it is not clearly written and in serious need of sourcing. —David Eppstein (talk) 20:56, 14 January 2014 (UTC)

The Boolean Assumption

The proof that a program halts or loops is entirely predicated on the assumption that the answer is a boolean yes/no. If you allow the 'halting detector' to answer with meta data, then it cannot be logically negated nor will the diagonalization approach work. It is the framing of the problem itself which gives rise to the paradox. Our human concept of 'halts' is semantically flawed when applied in this situation. This proof (and all its variations) only prove that such a 'halting detector' cannot function perfectly with only a boolean output. That is all. — Preceding unsigned comment added by 24.230.48.25 (talk) 18:14, 21 December 2014 (UTC)

The original problem asks for a boolean output. Moreover, I guess even if the answer may be chosen from a set (of "meta data" - whatever that could be) with more than 2 elements Turing's proof could be adapted to this more general situation. Anyway, a citation would be needed; if your idea leads to an entirely new theorem you should publish it in a scientific journal first. - Jochen Burghardt (talk) 18:11, 22 December 2014 (UTC)

To avoid self-reference

Can we avoid self-reference for this problem to solve it? Like Class (set theory)?

Please direct such questions to the Mathematics Reference Desk, WP:RD/Math. This page is for discussing potential changes to the article, not the subject of the article. --Trovatore (talk) 06:44, 11 August 2015 (UTC)

Contradictory information?

I'm just a layperson, but I'm confused that this page claims that the halting problem is undecidable, but the Wikipedia page on Hypercomputation states that "Siegelmann showed in her 1993 PhD thesis,[1][page needed] and later in her 1998 book,[9][page needed] that the halting problem of Turing machines can be solved with analog recurrent neural networks."

The reference in [1] is http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.38.920&rep=rep1&type=pdf, can someone who understands the science and math explain which statement is correct? 2A02:C7D:1A37:600:3023:B0C0:8CF6:1819 (talk) 22:02, 10 January 2016 (UTC)

I think, both are. Something being "undecidable" means that there is no Turing machine that decides it. "Analog recurrent neural networks" are a different, imho more esoteric, formalism; they are able to perform computations with infinite precision in a finite amount of time, and hence are more powerful. Note that both formalism are just mathematical models, which do not exist in the real world. - Jochen Burghardt (talk) 23:01, 10 January 2016 (UTC)

The Hypercomputation page does say at the very beginning that "This includes various hypothetical methods for the computation of non-Turing-computable functions." The halting problem is one of these functions. As Jochen Burghardt mentions, computability with analog neural networks is not a very widely used notion of computation. In general, unless someone is already talking about an atypical model of computation, when they say that a problem is undecidable they mean it is undecidable by Turing machines. — Carl (CBM · talk) 23:07, 10 January 2016 (UTC)

I slightly changed the wording of the involved sentence at Hypercomputation#Hypercomputation and the Church–Turing thesis, hoping to make it more clear. - Jochen Burghardt (talk) 14:56, 11 January 2016 (UTC)

What is "f" doing in "Sketch of Proof?"

Guys... What in the world is "f" doing in the sketch of the proof? Can't you do the same thing with just h, and without explaining the whole total computable function part of everything? Doesn't "f" really overcomplicate the sketch? Just say,

procedure compute_g(i):
    if h(i,i) == 0 then
        return 0
    else
        loop forever

And then run g(g)?

IE, how they explain it on pages 263-264 of Dasgupta's Algorithms? That's... a lot clearer. Like, a lot clearer. Even if it's a little less formal, this is a sketch of the proof, right? Daniel J. Hakimi (talk) 03:01, 19 November 2013 (UTC)

It's not really more clear that way, to the general population, because it makes people worry about the fact that you are using h inside a program, when h is not actually computable. By using f in the construction, we can point out that the construction does work for any total computable function f, so it must be the case that h is not equal to any total computable function. Otherwise, in your way of writing it, you have to say things like "of course compute_g is not computable, but if h were computable (even though it isn't) then the function compute_g would also be computable (even though it really isn't)." That just makes the proof more confusing. By using f, we can directly say that for every computable function f, the corresponding function compute_g really is computable. — Carl (CBM · talk) 18:00, 19 November 2013 (UTC)

I had to search the proof somewhere else to understand it because of the extra f. Not only that, but I think that the proof is wrong with the f: You cannot define a program e that computes g if g is defined in terms of a function f which can be any function. If you compile the program e as it is written it would say: function f is undefined, so it is not a valid program. — Preceding unsigned comment added by 129.12.41.233 (talk) 15:13, 26 March 2014 (UTC)

I would like to agree that the proof here is too complicated to be helpful for average readers. After going through the proof on this page for about 30 minutes, and assuming I understand it correctly, I think the gist can be given in a simple reductio ad absurdum argument. For example, assuming that halts(...) is a function which returns true for subroutines which halt and false otherwise, does the function below halt?

def paradox():
    if not halts(paradox): loop_forever()

I appreciate this might miss a lot of the mathematical subtlety. However, I suggest something along these lines is more helpful to casual readers who can then be directed to the more rigorous formulation. — Preceding unsigned comment added by 58.41.81.21 (talk) 12:04, 1 May 2014 (UTC)

The use of f(i,i) seems wrong to me. The first input to the halting function must be the program under consideration, which is g, right? It seems like f(i,i) should be replaced with f(g,i). Otherwise, the halting function is being computed on another program "i" and there is no contradiction. What am I missing? LaurenGrace05 (talk) 16:47, 26 October 2014 (UTC)laurenGrace

I think that I understand the proof here. The idea is that "h" is supposed to be a totally computable function if there is a universal solution to the Halting Problem, and the proof is to show that every single conceivable totally computable function with two arguments, "f", cannot be the same as "h". It also assumed (correctly under Turing mechanics), that an integer e can be created out of a program, and should be noted that "f" is being fed both with the program and its input in this proof.

That said, there is a conceptual error in the writing of the proof. The coup de grace of the proof is that h(e,e) returns 1 when f(e,e) is 0 (causing g(e) to return 0), and that h(e,e) returns 0 when f(e,e) ≠ 0 (causing g(e) to be undefined) - and that both of these differ from f(e,e), which is supposed to be any conceivable function. However, one could easily reconfigure the return values of h(i,j) such that it returns zero when program i halts on input j and 1 otherwise, which would make the first aforementioned case totally possible (when g(e) halts, h(e,e) returns 0 just as f(e,e) does), and the second case merely ambiguous (when f(e,e) could return pretty much any number, and if it returns 1, h(e,e) also returns the same value), which means that h could actually be equivalent to f. And if it can subsequently be proven that all functions that return either 0 or 1 can be mapped to functions returning all possible values, then this proof is entirely invalidated.

So, either our proof merely needs more consistent rewriting, it needs to be scrapped and entirely rewritten using different constructs entirely (preferably ones that are more central), or we, my friends, have just discovered that the Halting Problem is, indeed, no longer proven to be unsolveable, and respectable computer scientists can now go about finding a solution for it.

Compynerd255 (talk) —Preceding undated comment added 02:21, 16 October 2015 (UTC)

This short proof of the halting problem is known to me to be deeply flawed. Posit the following: The language does not have global variables and all function calls have copy input semantics (i.e. a pure functional language at the function level) and has by specification an optimizing compiler that runs h() across loops within the function (by inserting return 0 after each loop in turn so that they are functions again) replacing any loop found to be infinite with "return 0". If the compiler cannot resolve the second argument to h() at compile time it must then insert the call at runtime. Thus compute_g is transformed by the compiler to "procedure compute_g(i) if f(i,i) = 0 then return 0 else if !f(i,i) = 0 then return 0 else return 1" which we can prove reduces to "procedure compute_g(i) return 0" If you change the definition of compute_g(i) to use "return 1" instead of "return 0" you get "procedure compute_g(i) if f(i,i) = 0 then return 1 else if !f(i,i) = 0 then return 0 else return 0" which we can prove reduces to procedure compute_g(i) if f(i,i) = 0 then return 1 else return 0". Proving h() does not exist is harder. 104.220.91.194 (talk) 20:33, 7 January 2018 (UTC)JH

Why not solvable???

We can make a program, like mathematica and maple, etc. It can avoid self-reference (e.g. in Microsoft Excel, if you type "=A1+1" in A1, then Microsoft Excel will return "self-reference"), we can add this to our program, and if we type "def g(): if halts(g): loop_forever()" to it, since it is self-reference, our program immediately return "self-reference", and thus our program can determine whether a given program will finish running or continue to run forever. — Preceding unsigned comment added by 117.19.182.48 (talk) 21:12, 15 May 2018 (UTC)

Please direct such questions to the Mathematics Reference Desk, WP:RD/Math. This page is for discussing potential changes to the article, not the subject of the article. --Trovatore (talk) 21:23, 15 May 2018 (UTC)

Why the reversion

Hi,

Jochen Burghardt (talk · contribs) just removed a whole paragraph, about lossy computation in the "generalization" section, with the edit message "actually, en.wikipedia.ord implements such a machine (cf. "Applications" section, p.93, in the cited article)". I guess «cited article» refers to Abdulla, Parosh Aziz; Jonsson, Bengt (10 October 1996). "Undecidable Verification Problems for Programs with Unreliable Channels". Information and Computation. 130 (1): 71--90. doi:10.1006/inco.1996.0083. which is quoted in the deleted paragraph. In particular since this article contains indeed a page 93. However, neither this page nor this article contains no "application" section. And its seems strange to state that wikipedia implements a machine.

This is why I come here on this talk page and ask for more explanation about this removal.Arthur MILCHIOR (talk) 17:19, 2 April 2019 (UTC)

@Arthur MILCHIOR: Sorry, I overlooked your above text until now. - I considered your edit as a joke since (1) you did it on Apr 1st, (2) you cited page 92, which is outside the given page range 71-90, (3) I can't image any useful property that can be shown about a Turing machine where tape cells can be changed randomly (in particular, since the TM under consideration may behave like an ordinary TM, and since the deciding TM's tape may be arbitrarily messed up, I see no way to solve halting problem), and (4), as far as I remember, I couldn't find anything about lossy Turing machines or/and the halting problem in the article. So my edit summary was intended to say "I understood your joke". - Jochen Burghardt (talk) 18:51, 4 May 2019 (UTC)

Oops. I didn't pay attention to the date. I can totally see how it may seems to be an april fool's prank. I have too much respect for wikipedia to do that, but you can't know this.

Furthermore, you are entirely right, my citation was not correct. I cited the wrong article. The correct article was published the same year, and written by the same author. It is now corrected.

The lossy formalism does not allow to arbitrarily mess up the Turing machine. It only allows to remove elements from the tape, not to add any. I must admit that I don't know this domain well enough to know why they introduced the model in the first place. Otherwise, I would have written an article about lossy Turing machine. Such an article may be interesting, but I'm not qualified enough to write it. As far as I understand, the main idea is: what can occurs if your machine may arbitrarily loose access to a part of its memory. And the result state that, if you have no restriction over the kind of loss than you can have, then the halting problem become decidable. Mostly because there is no way to create back up fast enough to be sure that you won't keep loosing all of what you have computed yet. Arthur MILCHIOR (talk) 19:46, 4 May 2019 (UTC)

Thank you for your indulgence and your fixes.

I see now that the citation indeed covers the text (except that I couldn't find "primitive recursive" - where did you take that from?).

Abdulla and Jonsson don't mention Turing machines at all in their formal part; they just claim that their results generalize to lossy Turing machines (LTMs) in their introduction (p.92 lf) and their conclusion (p.100 lf). So I made some guesses: It seems that their LTMs are nondeterministic and "losing a symbol" means "cutting it out of the tape", rather than e.g. "replacing it by the blank symbol" (which was my first guess). Moreover, I guess they use their result in sect.5.4 for the halting problem, where the set of halting states is supplied as N. Maybe the "cut-out" semantics should be remarked in a footnote, since it seems to be quite unusual. - Jochen Burghardt (talk) 13:37, 13 May 2019 (UTC)

this is a very misleading and fuzzy article

In particular "Turing machine" and "computer program" are not similar but are used as synonyms. In fact, "computer programs" usually refers to programs that run on actual computers - which have finite state. Turing machines do not have finite state. The confusion of the two concepts leads to incorrect statements about the implications of the unsolvability of the Turing machine halting problem for programming. I tried to edit it, but I think it needs a rewrite. Yodaiken (talk) 14:40, 3 July 2019 (UTC)

According to e.g. Sipser, "Introduction to the Theory of Computation", Boston, 1997, p.125, Turing machines are used as a "more [compared to finite state automata or pushdown automata] accurate model of a general purpose computer". I think this viewpoint is very common in theoretical computer science. -

You are right than an actual computer can be decribed as finite automaton, and thus in theory can be checked whether it will eventually halt on a given program. However, e.g. a 32 GBit computer has 2^34359738368 possible states (ignoring registers etc.), so checking termination would need a computer with 2^34359738368 bits, this is far more than the number of elementary particles in the universe.

-

Which particular statements in the article do you consider incorrect? - Jochen Burghardt (talk) 18:27, 3 July 2019 (UTC)

Peeve alert: more than the number of elementary particles in the observable universe. The full universe may well be infinite. --Trovatore (talk) 17:32, 4 July 2019 (UTC)

Burghardt: the old and restored version is full of incorrect statements starting with "The theoretical conclusion of not solvable is significant to practical computing efforts, defining a class of applications which no programming invention can possibly perform perfectly." Which is false. The halting problem for Turing machines has no implications for the correctness problem for actual computer programs. Sipser is correct in that turing machines are sometimes used in analysis of algorithms (see, Garey&Johnso ), but the halting problem is not relevant to that use. Your statement is a good example of why the wording of the original article is misleading. You write: " You are right than an actual computer can be decribed as finite automaton, and thus in theory can be checked whether it will eventually halt on a given program." and therefore the Turing decision proof does not apply to actual computers. Of course the problem of determining whether computer programs will halt is HARD, but it is not undecidable. There is a huge difference: proved impossible and "seems hard" are not the same. My main objection ot the original wording is that theorems have precise meanings: the decision problem for actual computer programs and the decision problem for Turing machines is not the same. The exponential state issue of actual computers is possibly solvable - just as naive sorting methods are exponential but n log n methods have been discovered. Why don't you ask Sipser if he agrees with this reversion? Yodaiken (talk) 12:40, 4 July 2019 (UTC)

I reverted Yodaiken's changes because instead of equating Turing machines with programs, they equated Turing machines with algorithms, a worse mistake. —David Eppstein (talk) 21:45, 3 July 2019 (UTC)

Epstein. Your reversions are unwarranted. The word "program" and the word "computer" do not appear in Turing's paper. "Computer program" generally refers to a code that can run on an actual computer - see the Wikipedia entry under "computer program" e.g. "A computer program is a collection of instructions[1] that performs a specific task when executed by a computer." Turing machines are not computer programs or computers. Turing refers to "computable numbers" and "computable functions" and "processes" and explains that Turing machines are equivalent to Church's "effective functions". Look at the Wikipedia entry for "algorithm" and you will see a definition that is completely compatible with Turing's "process". Yodaiken (talk) 12:56, 4 July 2019 (UTC)

Eppstein's wholesale reversions also removed my much improved "informal" explanation of how the proof works. Look, if you want to keep a misleading article, go ahead. But if you check with experts, you will find I am right and the original page is misleading. Yodaiken (talk) 12:43, 4 July 2019 (UTC)

Calling a Turing machine an algorithm makes a mess of the start of Turing machine where it says 'A Turing machine is a mathematical model of computation that defines an abstract machine, which manipulates symbols on a strip of tape according to a table of rules. Despite the model's simplicity, given any computer algorithm, a Turing machine capable of simulating that algorithm's logic can be constructed." You may feel you are correct but I have seen no source which agrees with your way of putting things and usage in sources is what matters. Dmcq (talk) 16:42, 4 July 2019 (UTC)

Actually that sentence from the TM article is a bit awkward. A single TM is not a "model of computation"; rather, the notion of TMs is a model of computation. An individual TM is more like a program in that model. I completely agree that it's not an "algorithm", though. An algorithm is what's left of a program (or a TM) after you strip away implementation details. --Trovatore (talk) 17:28, 4 July 2019 (UTC)

I did not call a Turing machine an algorithm. But a Turing machine is definitely not a "computer program". A Turing machine is a conceptual device for executing algorithms. Turing uses "process" for what we would now call algorithm. In fact, I define a Turing machine correctly in one of the passages deleted.

That would be a good point if I had written that a Turing machine is an algorithm. Yodaiken (talk) 21:18, 4 July 2019 (UTC)

"A conceptual device for executing algorithms"? No. Each individual Turing machine executes implements only a single algorithm. For different algorithms, you use different Turing machines. That's why they're like programs.

I suspect you're thinking of a "universal Turing machine", which interprets its input to emulate other Turing machines. A UTM is indeed a TM, but again it executes implements only a single algorithm, namely the one for interpreting what's on the tape as a TM and emulating that TM. --Trovatore (talk) 05:56, 5 July 2019 (UTC)

You wrote "a general and powerful class of algorithms now called Turing Machines". How is that not calling a Turing machine an algorithm? —David Eppstein (talk) 21:58, 4 July 2019 (UTC)

You are right and I was wrong. I edited out the key phrase: "for a general and powerful class of algorithms that can be computed by what are now called Turing Machines" My apologies for making a hurried change and not proofreading carefully. The current article is still a mess but it was irresponsible of me to make these changes and try to keep up with the discussion during the holiday over a smart phone. Yodaiken (talk) 23:10, 7 July 2019 (UTC)

Haven't bothered to check the actual edits in question, but throwing in 2c anyhow: modern computers, being physical and not abstract, are neither finite automata nor Turing machines. But finite automata are a terrible abstract model of modern computers, while Turing machines are a very good abstract model of modern computers. And theorems about Turing machines are vastly more relevant to the behavior of actual computers than theorems about finite automata are. --JBL (talk) 19:40, 5 July 2019 (UTC)

Quite right especially as the tape of a Turing machine is only potentially infinite rather than actually infinite. A computer does not have an assigned size as potentially one can always write things to CDs or flash. All the matter in the universe and till all the black holes evaporate aren't exactly humanly finite limits like one thinks of for finite automata. Dmcq (talk) 23:16, 5 July 2019 (UTC)

If you are asking whether "a digital computer plus a person who will add an infinite number of CDs on demand" can solve a problem, you may get a different answer than if you ask whether Turing machines can solve the same problem. Same if you ask whether a computer and some supernatural agent that can convert all the matter of the universe into storage devices can solve that problem. That's why mathematicians try to state their premises precisely. Yodaiken (talk) 22:28, 7 July 2019 (UTC)

"Haven't bothered to check the actual edits in question, but throwing in 2c anyhow" par for the course here. Yodaiken (talk) 22:16, 7 July 2019 (UTC)

I do think though that it's reasonable to ask that the article explain that the argument treats the "programs" as running on an idealized computer, not a physical one. To treat physical computers in the argument, we'd have to use actual physics — the issue of finiteness is only one among many things that such an argument would have to take into account.

Surely there's an RS that treats this point? --Trovatore (talk) 00:18, 6 July 2019 (UTC)

Here's the point I keep trying to make. The "halting problem" theorem proved by Turing is a mathematical theorem, not a handwaving argument about some things being hard. It has a clear meaning and applies only to Turing machines, not to "computer programs" as defined in Wikipedia or in common usage. Yodaiken (talk) 22:16, 7 July 2019 (UTC)

It does NOT apply only to Turing machines. It applies to other mathematical idealizations that are much closer to actual computer programs running on actual computers. The one I usually have in mind is the RAM model but it also applies to programs in real languages like Python or Lisp where there is no built-in bound on the precision of the values or the number of different values that can be pointed to, as executed on idealized hardware that would allow such programs to use arbitrarily large amounts of memory rather than (as would happen in real life) eventually crashing when memory runs out. —David Eppstein (talk) 04:41, 8 July 2019 (UTC)

There may be problems you want to call "Halting Problems" for other models of computation. It may be that Turing's undecidability theorem implies that in those models the "Halting Problem" is also undecidable, but the theorem is about Turing machines, not about something else, and Martin Davis used "Halting Problem" to characterize the decision problem for Turing Machines (See page 70 of Davis) and in the intro "It is important that ... the reader carefully distinguish between formal definitions and more or less vague explanations". And re, python and Lisp, there is a huge difference between claiming that a machine can represent and work on arbitrary integers and claiming that it can represent integers within a finite range depending on some parameter. All this vagueness leads to imprecision and error. In particular it leads to confusion about what is hard because of computational complexity and what is not possible due to undecidability.

Yodaiken (talk) 15:17, 8 July 2019 (UTC)

If you want to argue about what may be, come back once you realize that all those things you say "may be" actually are known and standard. —David Eppstein (talk) 17:51, 8 July 2019 (UTC)

It's totally irrelevant if those things are "known" or "standard", whatever that means. The theorem is about Turing machines, not about RAM models or someone's feelings about how hard it would be to analyze actual programs. But I leave you to your error Yodaiken (talk) 21:58, 8 July 2019 (UTC)

@Yodaiken: Here is the first sentence of the Background section of the article: The halting problem is a decision problem about properties of computer programs on a fixed Turing-complete model of computation .... Maybe you should reflect more deeply on the fact that you have completely failed to convince several PhD-holding mathematicians and computer scientists to accept anything about your position, and change your approach. --JBL (talk) 13:16, 9 July 2019 (UTC)

Wow, an argument by authority. Very impressive. The best thing that could be done with this page is that it could be discarded and made to point to the https://wiki.riteme.site/wiki/Entscheidungsproblem which has the virtue of getting the math right. — Preceding unsigned comment added by Yodaiken (talk • contribs) 23:10, 11 July 2019 (UTC)

"Before the question could be answered, the notion of "algorithm" had to be formally defined. This was done by Alonzo Church in 1936 with the concept of "effective calculability" based on his λ-calculus and by Alan Turing in the same year with his concept of Turing machines. [...]

If 'Algorithm' is understood as being equivalent to a Turing Machine, and with the answer to the latter question negative (in general), the question about the existence of an Algorithm for the Entscheidungsproblem also must be negative (in general). In his 1936 paper, Turing says: "Corresponding to each computing machine 'it' we construct a formula 'Un(it)' and we show that, if there is a general method for determining whether 'Un(it)' is provable, then there is a general method for determining whether 'it' ever prints 0".

https://wiki.riteme.site/wiki/Entscheidungsproblem. Yodaiken (talk) 12:29, 9 July 2019 (UTC)

Gödel's incompleteness theorems

What is the reference for the proof of the incompleteness theorem from the halting theorem? — Preceding unsigned comment added by 47.152.156.71 (talk) 21:39, 13 January 2017 (UTC)

The first time I've seen the comparison between Turing's halting problem proof the incompleteness theorem was in Scott Aaronson's book "Quantum Computing since Democritus". The precursor to the book is this lecture series, and the content is quite similar as far as I can tell. See this lecture notes page https://www.scottaaronson.com/democritus/lec3.html. I would also like to see more discussion and references on this matter. 217.173.96.166 (talk) 14:04, 22 January 2020 (UTC)

2020

According to 'Quanta' magazine, a significant break-through was made in 2020. Can someone who understands this stuff take a look and make changes if necessary? — Preceding unsigned comment added by 213.109.221.152 (talk) 01:58, 26 December 2020 (UTC)

This seems to be the article. RE (complexity), Tsirelson's bound#Tsirelson's problem, and Connes embedding problem already list the paper, which seems sufficient coverage of the results. The issue I see is that none of those articles are linked to by this one, the closest is Computably enumerable which links to RE. So the thing to do in this article would be to mention that the halting problem is in class RE and link to it. --Mathnerd314159 (talk) 17:50, 26 August 2021 (UTC)

Sketch of a rigorous proof incomplete or erroneous

Hello everyone, There is an argument missing in the sketch of a rigorous proof: "It follows from the definition of g that exactly one of the following two cases must hold: - f(e,e) = 0 and so g(e) = 0. In this case h(e,e) = 1, because program e halts on input e. - f(e,e) ≠ 0 and so g(e) is undefined. In this case h(e,e) = 0, because program e does not halt on input e. 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."

As far as I know (I got a master's degree in theoretical CS), the third line should be "f(e,e) ≠ 0 and so g(e) is undefined. In this case the value of h(e,e) is unknown because program e either outputs 1 or does not halt on input e." And the concluding argument should then be something in the line of "The first case shows that any total computable function with two argument f must differ from h if there is a program able to halt. The identity function is an example of program always halting. Hence h is not a total computable function."

The explanation may be extracted from a book (Penrose 1990 is used as an in-text reference), if this is the case then either this is a mistake in the retranscription or the reference is wrong.

213.89.8.187 (talk) 19:20, 11 November 2021 (UTC)

g being undefined means the program e does not return a value (i.e., runs forever). Program e cannot output 1, because then g(e) would be 1. Since e(e) runs forever, h(e,e) is 0 by definition of h. So when you say "the value of h(e,e) is unknown" this is not the case. I would suggest looking at the pseudocode for e. --Mathnerd314159 (talk) 03:20, 30 November 2021 (UTC)