0
$\begingroup$

Let's say program $P$ with given input $i$ is found to halt (or doesn’t halt) by a Turing machine. Is it true that the same program $P$ with input $F(i)$ also halts (or not, respectively), where $F$ is a computable function?

In general, is it true that the behavior of program $G(P)$ with the input $F(i)$ identical to the behavior of P with input i? (Both $G$ and $F$ are computable.)

| cite | improve this question | |
$\endgroup$
  • 1
    $\begingroup$ Please don't delete your question and then re-ask it. cs.stackexchange.com/q/116593/755 $\endgroup$ – D.W.♦ Nov 4 '19 at 2:43
  • 1
    $\begingroup$ I can't tell what you are asking. What do you mean by "found to halt by a Turing machine", specifically? Why would you think that the behavior of P on input i would be at all related to its behavior on a different input (such as F(i))? What are your thoughts on this problem? Have you tried to solve it yourself? Have you tried to construct an example of P,F,i where the answer is yes? Have you tried to construct an example where the answer is no? What partial progress have you made so far? $\endgroup$ – D.W.♦ Nov 4 '19 at 2:44
  • $\begingroup$ @D.W. By "found to halt" I mean a Turing machine that runs it will halt and gives an output. I think whether P[F(i)] halts is related to whether P(i) halts because it seems that running P[F(i)] is just running F(i) (which halts since F is computable) followed by running P with F(i) as input. $\endgroup$ – Danny Nov 4 '19 at 4:44
0
$\begingroup$

No, it is not.

In general, to help you think about this kind of problem, I recommend you work through some examples. Keep them as simple as possible.

Here is an example that illustrates why the answer is no. Suppose $P$ is the following program: "if the input is 1, then halt immediately; otherwise enter an infinite loop". Suppose $F(1)=2$. Then $P$ halts on the input $i=1$, but it does not halt on the input $F(i)=F(1)=2$. So, the behavior of the program $P$ on one input tells you nothing about its behavior on a different input.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thanks. It is very clear by looking at specific examples. I have another question though, it seems we can transform the program to a new one that halts with the input $F(1)$. In the example you gave, this new program is "if the input is 2, then halt immediately; otherwise enter an infinite loop". Is this always true? i.e. there always exist $H(P)$ that halts for input $F(i)$, where $H$ is computable? $\endgroup$ – Danny Nov 4 '19 at 7:49
  • $\begingroup$ @Danny, sorry, this platform doesn't work very well for interactive conversations or follow-up questions, and I won't be able to look at that right now. I suggest spending some time thinking about it, trying to work through some examples, and if you still can't solve it, ask a new question, make it self-contained, and show your work. $\endgroup$ – D.W.♦ Nov 4 '19 at 8:13

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.