1
$\begingroup$

Currently I'm reading about the Halting problem. $H(\langle M,w\rangle)$ is a machine which will solve the Halting problem, and then using machine $H$ one creates a new machine $D$ and we run $H$ on input $\langle M, \langle M\rangle\rangle$.

My question is: What is the significance of giving a description of Turing machine as input as in $\langle M,\langle M\rangle\rangle$?

What is the logical reason behind giving the description of a Turing machine as input to $D$?

$\endgroup$
  • 1
    $\begingroup$ Are you asking "how would one get this idea?" or "why do we need this?". The latter question is moot: it turns out to show something important. Nobody says we have to go about it this way. $\endgroup$ – Raphael Oct 26 '16 at 22:17
  • 1
    $\begingroup$ The "significance" is that it turns out to be a useful concept. I don't understand what you're asking. $\endgroup$ – Raphael Oct 26 '16 at 22:19
  • $\begingroup$ yes how would one get this idea of giving description of TM as input, what if we input other string of 0 and 1's ? $\endgroup$ – user156991 Oct 27 '16 at 5:21
  • $\begingroup$ That's a historical question I don't know a definitive answer to. Strike of inspiration, maybe. I would guess the idea of a universal machine came first, and a machine taking encodings of other machines as input is just a necessity then. $\endgroup$ – Raphael Oct 27 '16 at 9:37
3
$\begingroup$

We can then think of the machine description $\langle M \rangle$ as the source code of $M$. If we do this, then the Halting Problem is really concerned with the decision problem

Given the source code of a program and an input string, will the program halt if fed the string as input?

There are many programs that take program code as input. A compiler is a well-known example; a specialized text editor is another.

If the Halting Problem were decidable, there would be a predictor program that could correctly predict the behaviour of any given program, given its source code. We could then modify the predictor program such that it would always behave differently from the program that it was analyzing. But then we could of course feed this modified predictor program its own source code and predict how it would react. And the conclusion would be that its behaviour would be different from its own behaviour -- and this is of course a contradiction.

$\endgroup$
1
$\begingroup$

One goal is to be able to process some machines by other machines, like one program processes another program. One doctor may operate on another human. The point of doing this in Turing Halting is to prove that there is no halting machine. The point of feeding a machine to a Halting machine is to check if your machine ever (always?) stops. Turing made a mental experiment where assuming that Halting machine exists, demonstrates that this leads to a contradiction and, thus, no Halting machine may exist.

You see, there can be many reasons you may want submit one machine as input to another. Turing argued that whatever what can he computed can be computed by Turing Machines and, checking the limits of Turing machines, he checked the limits of computation -- what can be ever computed and what cannot. And feeding one machine to the other plays important role in the evaluation of what is computable.

$\endgroup$
0
$\begingroup$

Some intuition can be found by considering the case of universal turing machine. This machine can simulate another turing machine for some arbitrary input. For this the universal turing machine takes as an input : The encoding of the turing machine and the input which has to be simulated on the machine which is fed as an input. The universal turing machine can be used to prove the halting problem.

$\endgroup$

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.