patternMinor
Why did Alan Turing have to define computation before demonstrating undecidability?
Viewed 0 times
whycomputationundecidabilityhavediddemonstratingdefineturingbeforealan
Problem
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."
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."
Solution
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.
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.
Context
StackExchange Computer Science Q#98958, answer score: 2
Revisions (0)
No revisions yet.