Turing machines Flashcards
Turing machine model
An infinite tape with letters of a certain alphabet on it. There is a reader/writer head that can move left and right in each step. The head starts at the right #.
Turing machine parameters <Q, Σ, δ, s, h>
Q: all the possible states that the machine might be in.
Σ: The input alphabet.
δ: The transition function. (δ:(Q-{h}) x Σ -> Q x Σ x {L,R,C})
s: starting state
h: end state
Configuration
A capture of the current state of the machine.
c = (Q?, #????, current letter, ???#)
A TM computes a function f(w) if:
hello
There is a certain number of transitions that lead from configuration (s, #w#) to configuration (h, #f(w)#)
Decidable language
A languadge L is decidable if there is a turing machine that can determine (in a finite amount of time) if a given string is in the language or not
e
Acceptable language
A language L is acceptable if there is a TM that will eventually accept and hault given a string w in L.
L is decidable -> L is acceeptable
True
L is acceptable -> L is decidable
False
L is decidable -> L̄ is decidable
True
L is acceptable -> L̄ is acceptable
False
Decidable languages are closed to ∪
True
Acceptable languages are closed to ∪
True
Post’s theorem
L̄, L are acceptable -> L is decidable
