patternMinor
undecidability proof by using Turing Machines
Viewed 0 times
undecidabilityusingmachinesturingproof
Problem
I have been reading some material about undecidability of a language, and I am not quite sure of one part. For what I see:
I start with a decider H, that has an input `` where M is a Turing Machine and w is a string, so I have the following:
all fine until this point. Now it says that I construct a new Turing Machine D, and this TM has H as a subroutine. If I make a graph I imagine something like this:
So it says that D calls H to determine what M would do if the input is M, it means something like:
Now it says that it should do the opposite this decider H, it means that:
and this procedure can be generalized for D like:
I have two questions here, for not opening another thread, but in part (1) why the decider H makes the opposite? What would happen if it does not? I have read in a book that the argument is that sometimes a program can receive a program as an input, such as in a compiler, why it decides to do the opposite?
The interpretation of part (2) does it mean that the Turing Machine D, with input M, this input refers to the same Turing Machine that was put as an input for the decider H?
At the ends there is a contradiction, but I cannot get it, why in step (1) it is decided to do the opposite?
I start with a decider H, that has an input `` where M is a Turing Machine and w is a string, so I have the following:
H()=accept if M accepts w
rejects if M rejects wall fine until this point. Now it says that I construct a new Turing Machine D, and this TM has H as a subroutine. If I make a graph I imagine something like this:
------------- D that is a TM
| ----- |
| | H | |
| |____| |
|___________|So it says that D calls H to determine what M would do if the input is M, it means something like:
H(M,)Now it says that it should do the opposite this decider H, it means that:
H(M,)=reject if M accepts
accepts if M rejects ---------(1)and this procedure can be generalized for D like:
D()=accept if M does not accept ----------(2)
reject if M accept I have two questions here, for not opening another thread, but in part (1) why the decider H makes the opposite? What would happen if it does not? I have read in a book that the argument is that sometimes a program can receive a program as an input, such as in a compiler, why it decides to do the opposite?
The interpretation of part (2) does it mean that the Turing Machine D, with input M, this input refers to the same Turing Machine that was put as an input for the decider H?
At the ends there is a contradiction, but I cannot get it, why in step (1) it is decided to do the opposite?
Solution
We have the language (commonly called $A_\text{TM}$):
$$
A_\text{TM}=\{(\langle M\rangle, w)\mid M\text{ is a TM and $M$ accepts $w$}\}
$$
and we want to show that this language is undecidable. We proceed by contradiction, assuming that there is a TM, $H$ that is a decider for $A_\text{TM}$. The action of $H$, when given a description $\langle M\rangle$ of a TM $M$ and a string $w$, is to accept if $M$, given $w$, accepts and to reject otherwise.
We use the purported decider $H$ to make another decider $D$ which takes as input a TM description $\langle M\rangle$ and sends that description to $H$, both as a machine description and as an input string (which answers your question (2): yes, we send $\langle M\rangle$ to $H$ as both inputs).
Now you've correctly interpreted the action of TM $D$:
$D$, on input $\langle M\rangle$, accepts if and only if $M$, on input $\langle M\rangle$, rejects.
In other words, $D$ always correctly determines whether a TM doesn't accept its own description as an input.
Which brings us to your question (1): why design the decider $D$ in such a peculiar way? The answer is precisely so that we can reach a contradiction. Since $D$ uses $H$ as a subroutine, it's clear that $D$ is a valid TM as long as $H$ is also. But now consider what happens if we give $D$ its own description as input? The action of $D$ on its own description is now
$D$, on input $\langle D\rangle$, accepts if and only if $D$, on input $\langle D\rangle$, rejects.
This contradictory behavior clearly is impossible, so our initial assumption, that there was a decider $H$, must be false. In other words, the language $A_\text{TM}$ must be undecidable.
$$
A_\text{TM}=\{(\langle M\rangle, w)\mid M\text{ is a TM and $M$ accepts $w$}\}
$$
and we want to show that this language is undecidable. We proceed by contradiction, assuming that there is a TM, $H$ that is a decider for $A_\text{TM}$. The action of $H$, when given a description $\langle M\rangle$ of a TM $M$ and a string $w$, is to accept if $M$, given $w$, accepts and to reject otherwise.
We use the purported decider $H$ to make another decider $D$ which takes as input a TM description $\langle M\rangle$ and sends that description to $H$, both as a machine description and as an input string (which answers your question (2): yes, we send $\langle M\rangle$ to $H$ as both inputs).
Now you've correctly interpreted the action of TM $D$:
$D$, on input $\langle M\rangle$, accepts if and only if $M$, on input $\langle M\rangle$, rejects.
In other words, $D$ always correctly determines whether a TM doesn't accept its own description as an input.
Which brings us to your question (1): why design the decider $D$ in such a peculiar way? The answer is precisely so that we can reach a contradiction. Since $D$ uses $H$ as a subroutine, it's clear that $D$ is a valid TM as long as $H$ is also. But now consider what happens if we give $D$ its own description as input? The action of $D$ on its own description is now
$D$, on input $\langle D\rangle$, accepts if and only if $D$, on input $\langle D\rangle$, rejects.
This contradictory behavior clearly is impossible, so our initial assumption, that there was a decider $H$, must be false. In other words, the language $A_\text{TM}$ must be undecidable.
Context
StackExchange Computer Science Q#67178, answer score: 4
Revisions (0)
No revisions yet.