Week 1 ( Turing machines + automatons)

Question 1

5 features of turing machine M

Answer 1

M = [ Σ, Q, qinit, qaccept, qreject, δ ]

.Alphabet Σ (finite set of symbols) {a1, ….,ak} | All three
. Finite number of States Q = {q1, … , qk} | Found in
.initial state | DFA, NFA

. Qaccept , Qreject ( specified single rejected and single accepted state)

. Transition function

δ (current state , read symbol) → (new state, write, move)

Transition function like in DFA UNIQUELY DETERMINES next state , HOWEVER it also determines whether we write a symbol to the tape (or leave it unchanged) , and whether we move the tape left or right

Question 2

Turing machine has how many outcomes

Answer 2

3

Question 3

what are these 3 outcomes?

Answer 3

Accepted:
Terminates on an accepted state

Rejected:
Terminates on a rejected state

.Undecided ( infinite) :
machine runs forever on input word never terminating

Question 4

M (turing machine)

M(w) := { 1 if M accepts w
{ 0 if M rejects w
{ ↑ if M does not halt ( infinite loop ) on w