1610906232-7ba7dbaea13262b50a6029d682cb7f1b (824370), страница 56
Текст из файла (страница 56)
It remains only tospecify some tiles to initiate the computation and ensure that the bottom rowis tiled correctly.(e) The origin tile do is illustrated in Figure 5-6(a). It specifies on its topedge the initial state 8 of M and the symbol 1>. That is, instead of having Mstart at configuration (8, 1>1J), we instead think that it starts at (8,!:,:); by ourconvention concerning 1>, its next configuration will definitely be (8, 1>1J). Theright edge of the origin tile is marked with the blank symbol; this edge can bematched only by the left edge of our last tile, shown in Figure 5-6(b), which inturn propagates to the right the information that the top edge of every tile inthe bottom row is marked with the blank.Figure 5-6This completes the construction of V. The set of tiles under (e) ensures thatthe border between the first two rows is mar ked (8, 1» U U U ...
; the other tilesforce each subsequent border to be marked correctly. Note that no tile mentionsany halt state, so that if M halts after n steps, only n rows can be tiled.Example 5.6.1: Consider the Turing machine{I>,U}, K = {8,h}, and 6 is given by6(8, 1» = (q, -+),6(8, U) = (8, +-).(K,~,6,8,{h}),where~266Chapter 5: UNDECIDABILITY(\', .\~~<-f-S,\(.'"q(\.~r, . \/~.~lWlWFigure 5-7This machine simply oscillates its head from left to right and back again, nevermoving beyond the first tape square. The tiling of the plane associated with theinfinite computation of M is shown in Figure 5-7.(>Problems for Section 5.65.6.1.
Let M = ({s},{a,u,I>},b,s), where b(s,u) = (s,a), and b(s,a) = (s,-+).Find the set of tiles associated with M via the construction in this section,and illustrate the first four rows of a tiling of the plane by means of thesetiles.5.6.2. Show that there is some fixed set of tiles D and adjacency rules H and Vsuch that the following problem is undecidable: Given a partial tiling, thatis, a mapping f : S .-+ D for some finite subset S C;;; N x N such that fobeys the adjacency rules, can f be extended to a tiling of the whole plane?5.6.3. Suppose the rules of the tiling game are changed so that instead of fixing aparticular tile to be placed at the origin, we fix instead a particular set oftiles and stipulate that only these tiles may be used in tiling the first row.Show that the tiling problem remains undecidable5.6.4.
Suppose the rules of the tiling game are changed as follows: The tiles arenot perfectly square, but may have various bumps and notches along theiredges. Two tiles may be laid down next to each other only if their edges fittogether perfectly, like pieces of a jigsaw puzzle; and only tiles with perfectlystraight sides can be used at the edges. Show that the tiling problem remains5.7: Properties of Recursive Languages267undecidable, even if we are now allowed to rotate tiles or turn them over.(There is no specified "origin tile" in this version.)5.6.5. Suppose that we think of square tiles as being determined by the colorsof their four edges, and that two edges may abut provided that they aresimilarly colored.
Show that if we are allowed to rotate tiles and turn themover, then any nonempty set of tiles can be used to tile the entire firstquadrant (even when we continue to require that one special tile be placedat the origin).liiJPROPERTIES OF RECURSIVE LANGUAGESWe have already seen that every recursive language is recursively enumerable,but the two classes are not the samp: The language H is one that bears witnessto the difference. Which recursively enumerable languages are recursive? Thereare many ways to answer this question; we present one next.Theorem 5.7.1: A language is recursive if and only if both it and its complementare recursively enumerable.Proof: If L is recursive, then L is recursively enumerable by Theorem 4.2.1;also, L is recursive, and hence recursively enumerable, by Theorem 4.2.2.For the other direction, suppose that L is semidecided by M1 and L issemidecided by M 2 • Then we can construct a Turing machine M that decidesL.
For convenience, we describe M as a 2-tape machine; by Theorem 4.3.1, Mcan be simulatpd by a I-tape machine. The machine M begins by putting itsinput string w on both tapes and placing its heads at the right ends of bothcopies of the input. Then M simulates both M1 and M2 in parallel: at eachstep of the operation of lvi, one step of M1 's computation is carripd out on thefirst tape, and one step of M 2 's computation is carried out on the second tape.Since either Ml or M2 must halt on w, but not both, M eventually reaches asituation in which the simulated version of either MI or M2 is about to halt.When this happens, M determines which of MI and M2 was about to halt, andhalts on y or n accordingly.•There is an interesting alternative characterization of recursively enumerable languages: They are precisely those that can be enumerated by some Turingmachine.Definition 5.7.1: We say that a Turing machine M enumerates the languageL if and only if, for some fixed state q of M,L= {w:(s,I>b!) t-A! (q,l>b!w)}.268Chapter 5: UNDECIDABILITYA language is Turing-enumerable if and only if it there is a Turing machinethat enumerates it.That is, M enumerates L by starting from blank tape and computing away,periodically passing through a special state q (not a halting state).
Enteringstate q signals that the string currently on M's tape is a member of L; Mmay then leave state q and reenter it later on with some other member of Lon its tape. Notice that the members of L can be listed in any order and withrepetitions.Theorem 5.7.2: A language is recursively enumerable if and only if it is Turingenumerable.Proof: Suppose that L is semidecided by Turing machine M. Then we candesign a machine M' which, instead of taking a string as input, starts from theempty tape, systematically generates (for instance, in lexicographic order) allstrings over the alphabet of L, and carries out on each the same computationthat M would carry out. Unfortunately, the obvious way to achieve this goalmay not work: Our new machine M' cannot hope to finish its computation oneach string before beginning to work on the next, since it may get "hung up"forever on some string for which the calculation by M does not terminate, eventhough there are other strings M would accept that have not yet been generated.(This strategy would of course work if L were decided by M; see the proof of thenext theorem.)The solution is based on a version of the the "dovetailing" procedure we usedin Section 1.4 to show that a union of countably many sets is countable.
Insteadof attempting to complete the computation on each string as it is generated, M'carries out the following sequence of operations:(Phase 1) First M' carries out one step of the computation of M on the(lexicographically) first string over the alphabet of M.(Phase 2) Then it carries out two steps of the computation of M on each ofthe first two strings.(Phase 3) Then it carries out three steps of the computation of M on eachof the first three strings, and so on.The first time M' discovers that M would accept a string, say WI, M' writeson its tape and pauses in state q to signal that WI E L.In general, after the ith string in L has been discovered, call it Wi, M' firstdisplays it at state q, and starts all over from Phase 1, and so on, keeping Wi onits tape.
Whenever it now discovers a string accepted by M, it first comparesit with Wi; if they are unequal, it continues. If it finds that the string justdiscovered is the same as Wi, then it looks for the next string accepted by M.WI5.7: Properties of Recursive Languages269This next string will be Wi+l. Again, Wi+l is displayed at state q, remembered,and compared. It is clear that any member of L will eventually be displayed.The other direction is somewhat easier.
If M enumerates L, then we canmodify M to semidecide L as follows: Redesign M so that it saves any inputsupplied to it before beginning its enumeration process. Furthermore, everytime M would enter the distinguished state q, the modified machine comparesthe current tape contents with the saved input string. If a match is found, theinput string is accepted; otherwise, the enumeration process continues. The newmachine then semidecides exactly the language enumerated by M .•How about recursive languages? It turns out that they can be enumeratedin a more orderly fashion.Definition 5.7.2: Let M be a Turing machine enumerating a language L. Wesay that M lexicographically enumerates L if the following is true, where q isthe special "display" state: Whenever (q, t>Jdw) f-t (q, t>Jdw l ) , then Wi comes lexicographically after w. A language is lexicographically Turing-enumerableif and only if it there is a Turing machine that lexicographically enumerates it.Theorem 5.7.3: A language is recursive if and only if it is lexicographicallyTuring-enumerable.Proof: Suppose that M is a Turing machine that decides L.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
