3
$\begingroup$

It seems to me that Turing could've just presented the following argument:

Theorem: Given a computational model $\mathcal{M}$ capable of conditional branching and indeterminate repetition the halting problem of $\mathcal{M}$ is undecidable from within $\mathcal{M}$.

Proof: Suppose $H$ solves the halting problem in $\mathcal{M}$. Namely $H\in\mathcal{M}$ and $$ H(A) = \begin{cases} 1 & \text{if $A(A)$ halts}\\ 0 & \text{if $A(A)$ doesn't halt} \end{cases}\qquad\forall A\in\mathcal{M} $$

Then construct $$ \begin{split} \overline{H}(A) & = \begin{cases} \infty & \text{if $H(A) = 1$}\\ 0 & \text{if $H(A) = 0$} \end{cases}\\ & = \begin{cases} \infty & \text{if $A(A)$ halts}\\ 0 & \text{if $A(A)$ doesn't halt} \end{cases} \end{split} $$ ($\infty$ indicates an infinite loop. The $0$ could've just as well been a $1$ without affecting the argument.)

Because $H\in\mathcal{M}$ so is $\overline{H}$. After all, it only adds conditional branching and an infinite loop. So we can ask whether $\overline{H}(\overline{H})$ halts - yielding a contradiction in either case. $$\tag*{$\Box$}$$

It seems to me that with this argument Turing could've just said "I don't care how you define computation. Try coming up with the most powerful notion you can conceive of, then run through this argument, and voila, there's still undecidable problems."

$\endgroup$
  • $\begingroup$ Yes, you are correct. That line of argument has been noticed by many people including, afaicr, Turing himself. Professor Eric C.R. Hehner also uses it to argue that the halting machine constructed by Turing is logically inconsistent in the same way as (or in a similar way to) Bertrand Russell's definition of a barber, hence does NOT show the undecidability of halting problem. You can check Reconstructing the Halting Problem and Problems with the Halting Problem. $\endgroup$ – John L. Oct 23 '18 at 9:23
  • 3
    $\begingroup$ "A computational model that is capable of conditional branching and indeterminate repetition". Well, if you have to be even more precise, you may have to come up with Turing machine or something equivalent as well. So, in that sense, you have not say anything new except a succinct summary or understanding of Turing's proof. $\endgroup$ – John L. Oct 23 '18 at 9:33
  • $\begingroup$ I am not good at that part of history. But I believe it is more fair to say that Turing wants to define computability first and then he discovers/proves the undecidability of halting problem. So it is a wrong assumption/connotation that Alan Turing wants to define computation in order to demonstrate undecidability. (I should have said, yes, you are somewhat correct instead of just you are correct) (I should write an answer instead.) $\endgroup$ – John L. Oct 23 '18 at 9:39
  • $\begingroup$ @Apass.Jack "So it is a wrong assumption/connotation that Alan Turing wants to define computation in order to demonstrate undecidability." This is what is claimed here: youtu.be/IOiZatlZtGU?t=252 $\endgroup$ – Sebastian Oberhoff Oct 23 '18 at 10:01
  • $\begingroup$ @Apass.Jack Also the link you provided to Reconstructing the Halting Problem just baffles me. It seems to me that the author has simply re-proven Rice's theorem and somehow concludes from that that the halting problem is ill-defined. $\endgroup$ – Sebastian Oberhoff Oct 23 '18 at 11:03
2
$\begingroup$

Well, I would like to ask the same kind of question to you.

Why did Sebastian Oberhoff have to define a computational model before demonstrating undecidability?

I will answer the above question on behalf of you below, assuming an imaginary line of case development. Of course, you might answer better than me.

Of course, to prove some kind of undecidability, I have to define what it is about. It should be about a general computation model. Whether it is Turing machine, $\lambda$-calculus, or recursive functions, it does not matter much. But I have to define exactly the meaning of a computation model so that I can proceed to prove some undecidability with mathematical rigor. My initial thought was that a computational model means some kind of machine that is capable of conditional branching and indeterminate repetition. Then I realized it must be able to simulate another machine of the same kind. So it should be able to encode program as data and decode data as program. It should have some kind of memory. Also it should be able to recognize its own state. And finally I have reached/discovered the basic requirement of a computation model, which, to my surprise, is basically equivalent to what have been found by the father of computer science, Alan Turing, Turing machine. Henceforth, I will humbly refer to my theorem and proof as a modern version of Alan Turing's result.


With this argument Turing could've just said "I don't care how you define computation. Try coming up with the most powerful notion you can conceive of, then run through this argument, and voila, there's still undecidable problems."

Yes, just as you suspected, Turing did write the same idea with more mathematical rigor. Here is an excerpt from Wikipedia entry on hypercomputation.

A computational model going beyond Turing machines was introduced by Alan Turing in his 1938 PhD dissertation Systems of Logic Based on Ordinals. This paper investigated mathematical systems in which an oracle was available, which could compute a single arbitrary (non-recursive) function from naturals to naturals. He used this device to prove that even in those more powerful systems, undecidability is still present. Turing's oracle machines are mathematical abstractions, and are not physically realizable.

$\endgroup$
  • $\begingroup$ My point was really: Hilbert asked for an algorithm for the Entscheidungsproblem. It was understood what the basic capabilities of an algorithm were. So this argument should've been sufficient for Hilbert's purposes. $\endgroup$ – Sebastian Oberhoff Oct 23 '18 at 17:19
  • $\begingroup$ Sorry that my humor is misunderstood. I hope you did notice that I said "humbly" before that. If you prefer, I would remove "humbly" as well. $\endgroup$ – John L. Oct 23 '18 at 17:25
  • $\begingroup$ Nevermind, we're good. $\endgroup$ – Sebastian Oberhoff Oct 23 '18 at 17:29
  • $\begingroup$ Thanks you for pointing out "Alan Turing wants to define computation in order to demonstrate undecidability". That seems more plausible with the link youtu.be/IOiZatlZtGU?t=252 you provided. $\endgroup$ – John L. Oct 23 '18 at 17:42
  • $\begingroup$ Yes, your argument should've been sufficient for solving Hilbert's Entscheidungsproblem, once a sufficiently clear definition of algorithm or computation is provided. $\endgroup$ – John L. Oct 23 '18 at 19:25
2
$\begingroup$

Without fixing a concrete model of computation, you can't show that you can actually do the "then construct" part of your argument, so it's not a proof.

$\endgroup$
  • $\begingroup$ I don't see why more specificity is required than just asking that the model allow for conditional branching and infinite loops. Those are the only things that are added in the construction. $\endgroup$ – Sebastian Oberhoff Oct 23 '18 at 12:44
  • $\begingroup$ Well, for a start, you're assuming the ability to use programs as subroutines. You're also probably assuming the ability to read some sort of input, which you don't mention as an assumption. $\endgroup$ – David Richerby Oct 23 '18 at 12:46
  • 1
    $\begingroup$ I would've thought that, since we're discussing models of computation, these things were implicit. But in any case, you can just add these assumptions if you like. $\endgroup$ – Sebastian Oberhoff Oct 23 '18 at 12:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.