What people are saying - Write a review
We haven't found any reviews in the usual places.
Incomplete Sequential Machines
3 other sections not shown
Other editions - View all
1-automaton 2-regular abstract machine closed family compatible complete sequential machine congruence relation connected machines Consider contradiction defined Definition Denote distinguished machine equivalence classes equivalence relation Et_i Et+i Example Exercise exists a tape Figure finite index finite number finite sets free semigroup function given in Fig Hence holds I2 Pi Pi incomplete induction input-distinguished input-equivalent input-output sequences integer isomorphic It_i It+i Iu_ih left cancellation law Lemma machine in Fig minimal-state machine nondeterministic automaton nonempty nonempty set Notation ordered pairs output sequence output-empty Pi E2 Pi P2 Pi V2 positive integer qi+i quasimachine recognition device regular sets result right invariant Rk+i satisfy the left sequential switching circuit set of tapes set union smallest possible number subset Suppose symbol tape of length Theorem Theorem 4.4 Turing machines two-tape automaton uniform experiment X(gi X(pi Xs(g Xs(p