Definition 8.1.1: a Turing acceptor T is a 7-tuple T = (S, _______, s0, b, R), where S (states) is a finite non empty set, _ (tape alphabet) is a finite non empty set, ______(input alphabet) is a non empty set, s0_S (start state), b____ (blank symbol), R _ S (recognizing or accepting states), and _: S___--> S___{l, r} is the (partial) next-move function.
Definition 8.1.2: an instantaneous description (ID) for Turing machine T = (S, _______, s0, b, R) is a sequence _1s_2 where s_S and _1_2__*; note that blank symbols atthe right of _2 may be omitted.
Previous slide | Next slide | Back to first slide | View graphic version |