I’m not convinced f(n) := f(n) should be considered inequivalent from f(n) := f(n+1) - neither coterminates.
I agree that these look tractable.
Given a program O for the first problem, a sufficient condition for M would be M(x) = O(M, x). This can be implemented as M(x) = O(M’(M’),x), where M’(M″,x) = O(M″(M″),x).
I’d call it an instance of https://en.wikipedia.org/wiki/Equivalence_problem—although unusually, your language class only admits one word per language, and admits infinite words.
I’m not convinced f(n) := f(n) should be considered inequivalent from f(n) := f(n+1) - neither coterminates.
I agree that these look tractable.
Given a program O for the first problem, a sufficient condition for M would be M(x) = O(M, x). This can be implemented as M(x) = O(M’(M’),x), where M’(M″,x) = O(M″(M″),x).