This seemed like the least inappropriate place for this. Feel free to move it if I am wrong.(adsbygoogle = window.adsbygoogle || []).push({});

Generally speaking, two computational models are equivalent if theyrecognizethe 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?")

**Physics Forums | Science Articles, Homework Help, Discussion**

Join Physics Forums Today!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

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

**Physics Forums | Science Articles, Homework Help, Discussion**