Dismiss Notice
Join Physics Forums Today!
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

  1. Feb 17, 2012 #1
    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?")
  2. jcsd
  3. Feb 17, 2012 #2


    User Avatar
    Science Advisor

    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?
  4. Feb 17, 2012 #3
    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
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook