Models of Computation Flashcards
1
Q
True or False: All recognizable languages are decidable
A
False. Consider the language HALT = {<M, w>: M is a TM and M halts on w}, a recognizable but undecidable language. Note that the opposite is true: all decidable languages are recognizable
2
Q
Church-Turing Thesis
A
A basic TM can simulate any algorithm (any mechanical procedure)
3
Q
What are the main models of computation that can be used to characterize main classes of languages
A
- DFA (Deterministic Finite Automaton)
- PDA (Pushdown Automaton)
- TM (Turing machine)
4
Q
What are the main classes of languages
A
- regular
- context free
- decidable
- recognizable
- decision problems
