# Decidable questions of undecidable problems

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?

• "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? – orlp Oct 10 at 7:52
• @orlp I have edited the question to mention that the finite extra steps halts. – Danny Oct 10 at 8:38
• 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. – Noah Schweber Oct 11 at 20:47
• @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. – Danny Oct 13 at 7:58

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.