Equivalence of models with respect to Turing-recognizability and -decidability

[alexfloo]

This seemed like the least inappropriate place for this. Feel free to move it if I am wrong.

Generally speaking, two computational models are equivalent if they recognize the same class of languages. In the case of models that can run indefinitely, we also have the problem of decidability. Generally, we make no mention of decidability in equivalence proofs.

I understand that a Turing-recognizable language is decidable if and only if its complement is Turing-recognizable. Can this fact be used to prove that a model decides the decidable languages if and only if it recognizes the Turing-recognizable languages?

Can it be shown more generally two models decide the same languages if and only if they recognize the same languages?

Clearly this problem isn't completely specified, since to my knowledge a "model of computation" is as loosely defined today as an "algorithm" was pre-Turing. (By the way is there any theory about something resembling a "category of computational models?")

 

[chiro]

Hey alexfloo.

In terms of the language, does one language have to be the same or can it be a subset of the other language?

 

[alexfloo]

I actually managed to find a partial answer, which is that even my first question was ill-formed.

The enumerator is equivalent to the TM in that they recognize the same languages, but enumerators decide exactly the finite languages. For any infinite language, an enumerator enumerates infinitely.

Furthermore, it raises the point that a model (at least until we have a better definition of it) need not "decide" at all.

For instance, we have the trivial model "the set" which accepts if it contains a string and rejects otherwise. It recognizes the class of all languages, unrestricted. It may make sense to say that it decides the same languages it accepts, but it illuminates that a model may not have a parallel as a "process" which can "run infinitely" or "not run infinitely," and decidability need not make sense with respect to any model