Schaum's Outline of Discrete Mathematics, Third Edition (Schaum's Outlines)

CHAP. 13] FINITE STATE MACHINES AND TURING MACHINES 325 wheres 0 is the initial state, while printing a string (word) of output ...

326 FINITE STATE MACHINES AND TURING MACHINES [CHAP. 13 Fig. 13-2 13.3Gödel Numbers Recall (Section 11.5) that a positive intege ...

CHAP. 13] FINITE STATE MACHINES AND TURING MACHINES 327 Basic Definitions ATuring machineMinvolves three disjoint nonempty sets: ...

328 FINITE STATE MACHINES AND TURING MACHINES [CHAP. 13 The above action byMmay be described by a five-letter expression called ...

CHAP. 13] FINITE STATE MACHINES AND TURING MACHINES 329 Computing with a Turing Machine The above is a static (one-step) descrip ...

330 FINITE STATE MACHINES AND TURING MACHINES [CHAP. 13 13.5Computable Functions Computable functions are defined on the set of ...

CHAP. 13] FINITE STATE MACHINES AND TURING MACHINES 331 Functions of Several Variables This subsection defines a computable func ...

332 FINITE STATE MACHINES AND TURING MACHINES [CHAP. 13 Fig. 13-4 (b) The state diagramD=D(M)appears in Fig. 13-4(b). Note that ...

CHAP. 13] FINITE STATE MACHINES AND TURING MACHINES 333 (b) Mis in states 2 and scanning the last letter of the tape expressionw ...

334 FINITE STATE MACHINES AND TURING MACHINES [CHAP. 13 13.9. Letfbe the functionf (x, y)=y. Show thatfis computable. We need to ...

CHAP. 13] FINITE STATE MACHINES AND TURING MACHINES 335 Fig. 13-7 TURING MACHINES 13.14. LetMbe a Turing machine. Determine the ...

336 FINITE STATE MACHINES AND TURING MACHINES [CHAP. 13 13.24. Letf be the functionf (n)=n−2 whenn>1 andf (n)=0 whenn=0 or 1. ...

CHAPTER 14 Ordered Sets and Lattices 14.1Introduction Order and precedence relationships appear in many different places in math ...

338 ORDERED SETS AND LATTICES [CHAP. 14 EXAMPLE 14.1 (a) LetSbe any collection of sets. The relation⊆of set inclusion is a parti ...

CHAP. 14] ORDERED SETS AND LATTICES 339 EXAMPLE 14.2 (a) Consider the setNof positive integers ordered by divisibility. Then 21 ...

340 ORDERED SETS AND LATTICES [CHAP. 14 14.3Hasse Diagrams of Partially Ordered Sets LetSbe a partially ordered set, and suppose ...

CHAP. 14] ORDERED SETS AND LATTICES 341 EXAMPLE 14.4 Apartitionof a positive integermis a set of positive integers whose sum ism ...

342 ORDERED SETS AND LATTICES [CHAP. 14 (b) LetAbe any nonempty set and letP (A)be the power set ofAordered by set inclusion. Th ...

CHAP. 14] ORDERED SETS AND LATTICES 343 EXAMPLE 14.6 (a) LetS={a, b, c, d, e, f}be ordered as pictured in Fig. 14-3(a), and letA ...

344 ORDERED SETS AND LATTICES [CHAP. 14 14.6Isomorphic (Similar) Ordered Sets SupposeXandYare partially ordered sets.Aone-to-one ...