Definition 8.1.4: a run of Turing machine T = (S, _______, s0, b, R) is just a sequence of moves of the machine; that is, there is a run from ID I1 to ID I2, I1 _* I2, provided there is a sequence of IDs J0, J1, , Jk (k0) so that I1 = J0, I2 = Jk, and Ji _ Ji+1 for 0i
Definition 8.1.5: for a Turing acceptor T, the language accepted (or recognized) by T is L(T) = {w__* | s0w _* _1s_2 for some s_R and _1_2__*}.
Definition 8.1.6: a language L ___* is (partial) Turing-recognizable if there exists a Turing machine T so that L = L(T); if there exists such a Turing machine T that halts for each x__*, then L is called total Turing-recognizable.
Previous slide | Next slide | Back to first slide | View graphic version |