I was reading about Turing Machines and the Halting Problem, i understand that you need an oracle to decide whether given input will halt or loop forever. But why do we need an oracle if we can include the halting status within the input itself?

What i mean is, given an input, in the encoding process of it, we can add the halting status as an Additive Identity to the input that will make it halt in a known finite time steps.

An example, assuming that a new model of computation (X) exists, (X) is a Universal Turing Machine and has the computational power to operate and halt after (N) time steps on any input, and (N) = same length of the input ... What can be said about the halting problem given the described situation?

  • 1
    $\begingroup$ I don't understand your question. What does it mean to add something to the input "as an additive identity"? If your model of computation has the property that every computation halts, the halting problem for that model is obviously trivial. Conversely, because it seems to be a restricted form of Turing machine, it can't solve the ordinary Turing machine halting problem, since even unrestricted Turing machines can't do that. $\endgroup$ – David Richerby Dec 15 '15 at 9:25
  • 3
    $\begingroup$ Adding halting information to the input is nothing but an oracle. Note that the input space then depends on the machine the inputs are given to -- that's not what we typically understand when we say "a problem instance". $\endgroup$ – Raphael Dec 15 '15 at 10:05
  • $\begingroup$ @David, sorry for confusion. What i mean is, we can have an input of (a), where (a) represents a value or an idea, we can transfer this to (a) + 0 as stated in the wikipedia page, here (0) doesn't affect the main value (a) but it is known to the machine that this symbol is a halting status (as mentioned by Raphael). ( Conversely, because it seems to be a restricted form of Turing machine, it can't solve the ordinary Turing machine halting problem ...), so can we say that model of computation as it have the same power of a normal TM and halts on any input, is more powerful than a normal TM? $\endgroup$ – ABD Dec 15 '15 at 11:08
  • $\begingroup$ @Raphael, that makes sense, thanks i will update it => (oracle), would you please re-phrase the last two sentences? I believe its the reverse, that is, the input space defines the machines operating time and its operating space. $\endgroup$ – ABD Dec 15 '15 at 11:08
  • 1
    $\begingroup$ I think the issue is what we understand inputs to represent; see also here. In computability theory, we typically consider inputs from $\Sigma^*$ for some finite alphabet $\Sigma$ (or something isomorphic), and a "problem" is a subset of that. So, yes, you can define an input space of pairs $(x, H)$ and require that TMs halt on $x$ if and only if $H=1$. It's easy to build such a machine. What does that tell you? $\endgroup$ – Raphael Dec 15 '15 at 12:34

Your Answer

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

Browse other questions tagged or ask your own question.