0
$\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?

|cite|improve this question
$\endgroup$
  • 1
    $\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 at 7:52
  • $\begingroup$ @orlp I have edited the question to mention that the finite extra steps halts. $\endgroup$ – Danny Oct 10 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 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 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.

|cite|improve this answer
$\endgroup$
  • $\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 at 8:26

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.