-1
$\begingroup$

Even if there is no general algorithm to decide if any program will halt, but there could be properties or meta-questions about the programs that is decidable. For example, given program $A$ and a program $B$ that is obtainable from program $A$ by adding in finite steps of calculations that halts. So if $A$ halts, $B$ definitely halts (and vice versa). A trivial example is $B = A$.

The question "Do $A$ and $B$ have the same behaviour?" is decidable (they either both halt or run forever), even if we do not know whether $A$ or $B$ halts or not.

My question: Is it true that, for any program $A$, there is always a non-trivial program $B$ such that there is a decidable meta-question about the duo $(A, B)$? (Non-trivial means $B ≠ A$ and $B$ is not obtainable from $A$ via adding extra finite steps that halts. In general, it means $B\neq f(A)$, where $f$ is a computable function.)

I wonder if there is a field of research on this type of meta-problems?

Improve this question
$\endgroup$
4
  • 2
    $\begingroup$ "Do A and B have the same behavior" is very much not decidable. If it were I could just set A to a known halting machine and then ask whether arbitrary program B halts by asking A = B? $\endgroup$ – orlp Oct 10 '19 at 7:52
  • $\begingroup$ @orlp I have edited the question to mention that the finite extra steps halts. $\endgroup$ – Danny Oct 10 '19 at 8:38
  • $\begingroup$ Your non-triviality requirement doesn't make sense: for any specific $A$ and $B$ (with any relationship at all) there is a computable function on Turing machine indices sending $A$ to $B$ - namely, just send everything to $B$. Precisely defining nontriviality in this context is going to be - appropriately enough - nontrivial. $\endgroup$ – Noah Schweber Oct 11 '19 at 20:47
  • $\begingroup$ @NoahSchweber, the non-triviality is suppose to mean one can’t find out about the computability of $B$, given the computability of $A$. I think sending $A$ to $B$ does not achieve that. $\endgroup$ – Danny Oct 13 '19 at 7:58
0
$\begingroup$

I'm not convinced by your setup. All programs are finite sequences of steps, so the equivalence of $A$ and $B$ in your first paragraph isn't decidable: they're equivalent iff $B$ halts on every input that $A$ halts on.

Your main question seems to be under-specified in a way that makes it trivial. The empty langauge is a decidable problem about pairs $(A,B)$. For any computable function $f$, the language $\{(A,B)\mid B=f(A)\}$ is decidable. But I suspect that any attempt to make the problem more precise will fail because of the issue I raised above.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thanks. I think you have stated what I was trying to capture. Can I amend the question to: by non-trivial it means B is not a computable function of A. $\endgroup$ – Danny Oct 10 '19 at 8:26
0
$\begingroup$

My interpretation:

There is no decidable language $L = \{(A,B)|B = f(A)\}$, where $f$ is non-computable and not semi-computable.

Proof: If $L$ was decidable there would be a Turing-Machine $T$ that decides it. We select $T$ in such a way that it has a single reject and a single accept state. This is possible since our language is decidable. Now we look at a specific Input $A$. We construct the Turing-Maschine $T_A$ that prints $A$ out and then runs $T$. $T_A$ basically "expects another input B". We know want to find an input to $T_A$ such that $T_A$ accepts. We can do that buy. Iterating through all strings $B$ and run $T_A$ on $B$. Since $T_A$ always halts we will either find a $B$ that results in an accept state or the procedure will run forever. Thus $f$ is semi-computable. This is a contradiction ans hence the statement is true.

Feedback? Is the proof correct?

Improve this answer
$\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.