0
$\begingroup$

There are other models of computation equivalent to Turing machines in terms of computability.

Turing machines also recognize recursively enumerable languages.

My questions are

  • Do other models of computation equivalent to Turing machines also recognize the same languages?
  • Are computability and language recognization unrelated to each other, so that other models of computation equivalent to Turing machines don't recognize or accept any language?

Thanks.

Improve this question
$\endgroup$

2 Answers 2

Reset to default
2
$\begingroup$

Two models of computation are equivalent iff they can compute exactly the same set of functions. So the answer to your question is yes, they can recognize the same languages. The definition of "accept" has to be altered a bit to fit the new model, of course, since for example in the lambda calculus you have no states that you could mark as accepting.

Improve this answer
$\endgroup$
1
$\begingroup$

Do other models of computation equivalent to Turing machines also recognize the same languages?

Yes. That's the definition of "equivalent to Turing machines"! In particular, to be equivalent to Turing machines, a model has to have something equivalent to not halting.

Are computability and language recognization unrelated to each other

Recognizing a language is computing membership of a set of strings; computing a yes/no function is recognizing the language "the set of strings that make the function true".

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.