Back to Home
Interactive Quizzes
Test your understanding of key concepts in computability theory
Decidability Concepts
The Halting Problem
Post Correspondence Problem
Decidability Concepts
Question 1 of 5
What does it mean for a language to be recursively enumerable?
There exists a Turing machine that accepts all strings in the language, but might not halt on strings not in the language.
There exists a Turing machine that accepts all strings in the language and rejects all strings not in the language.
There exists a Turing machine that generates all strings in the language.
There exists a Turing machine that can enumerate all strings in the language in lexicographic order.
Next Question