1610906232-7ba7dbaea13262b50a6029d682cb7f1b (824370), страница 52
Текст из файла (страница 52)
t But to continue withtLanguage implementors often write translators for a programming language in thesame programming language. But how is the translator to be itself translated?One way to do this is the following: Write the translator in a simple fragment ofthe same language, leaving out the more sophisticated (and difficult to translate)features of the language. Then write a translator for this fragment -a muchsimplified task- in an even more stripped-down version of the language.
Continuethis way until your language is so simple and explicit that it resembles an assemblylanguage, and so it can be directly translated in one.248Chapter 5: UNDECIDABILITYour project in this book we must make this point precise in th0 context of Turingmachines.To begin, we must present a general way of specifying Turing machines, sothat their descriptions can be used as input to other Thring machines.
That is,we must define a language whose strings are all legal representations of Turingmachines. One problem manifests itself already: ~o matter how large an alphabet we choose for this representation, there will be Thring machines that havemore states and more tape symbols. Evidently, we must encode the states andtape symbols as strings over a fixed alphabet. We adopt the following convention: A string representing a Turing machine state is of the form {q}{ 0, I} *; thatis, the letter q followed by a binary string.
Similarly, a tap0 symbol is alwaysrepresented as a string in {a}{ 0, I} * .Let !v! = (K, I:, 6, s, H) be a Turing machine, and let i and j be the smallestintegers sHch that 2i 2 IKI, and 2j 2 II:I + 2. Then each state in K will berepresented as a q followed by a binary string of length i; each symbol in I: willbe likewise represented as the letter a followed by a string of j bits. The headdirections +--- and -+ will also be treated as "honorary tape symbols" (they werethe reason for the "+2" term in the definition of j). We fix the representationsof the special symbols U, [>, +---, and -+ to be the lexicographically four smallestsymbols, respectively: U will always be represented as aO j , [> as aOj-1l, +--- asaO j - 2 10, and -+ as aO j - 2 11.
The start state will always be represented as thelexicographically first state, qOi. Notice that we require the use of leading zerosin the strings that follow the symbols a and q, to bring the total length to therequired level.We shall denote the representation of the whole Turing machine M as "M"."M", consists of the transition table 6. That is, it is a sequence of strings ofthe form (q; a, p, b), with q and p representations of states and a, b of symbols,separated by commas and included in parentheses. We adopt the convention thatthe quadruples are listed in increasing lexicographic order, starting with 6(s, U).The set of halting states H will be determined indirectly, by the absence of itsstates as first components in any quadruple of "M".
If M decides a language,and thus H = {y, n}, we will adopt the convention that y is the lexicographicallysmallest of the two halt states.This way, any Thring machine can be represented. We shall use the samemethod to represent strings in the alphabet of the Turing machine. Any stringw E I:* will have a unique representation, also denoted "w", namely, the juxtaposition of the representations of its symbols.2495.2: Universal Turing MachinesExample 5.2.1: Consider the Turing machine M = (K,I:,6,s,{h}), whereK = {s,q,h}, I: = {u,c>,a}, and 6 is given in this table.state,symbol6a(q, u)(h,u)(s, -+)(s, a)(s, -+)(q,-+)sssqqqUc>aUc>Since there are three states in K and three symbols in I:, we have i = 2and j = 3.
These are the smallest integers such that 2i 2: 3 and 2j 2: 3 + 2. Thestates and symbols are represented as follows:state I symbolrepresentationsqOOqOIq11aOOOaOOlaOlOa011alOOqhUc>+---+aThus, the representation of the string c>aa U a is"c> aa U a" = aOOlaIOOaIOOaOOOaIOO.The representation "}VI" of the Turing machine M is the following string:"M" = (qOO, aIOO, qOl, aOOO), (qOO, aOOO, q11, aOOO), (qOO, aOOl, qOO, a011),(qOl, aIOO, qOO, a011), (qOl, aOOO, qOO, a011), (qOl, aOOl, qOl, 011).<>Now we are ready to discuss a universal Turing machine U, which uses theencodings of other machines as programs to direct its operation.
Intuitively, Utakes two arguments, a description of a machine M, "}VI", and a description ofan input string w, "w". We want U to have the following property: U halts oninput "M" "w" if and only if M halts on input w. To use the functional notationfor Turing machines we developed in the last chapter,U("AI" "w") = "M(w)".Chapter 5: UNDECIDABILITY250We actually describe not the single-tape machine U, but a closely related 3tape machine U' (then U will be the single-tape Turing machine that simulatesU').
Specifically, U' uses its three tapes as follows: the first tape containsthe encoding of the current tape contents of M; the second tape contains theencoding of M itself; and the third tape contains the encoding of the state of Mat the current point in the simulated computation.The machine U' is started with some string "AI" "w" on its first tape and theother two tapes blank. (It does not matter how U' behaves if its input string isnot of this form.) First U' moves "M" onto the second tape and shifts "w" downto the left end of the first tape, preceding it by "c> u". Thus at this point thefirst tape contains "c> Uw".
U' writes in the third tape the encoding of the initialstate 8 of M, always qOi (U' can easily determine i and j by examining "M").Now U' sets about simulating the steps of the computation of M. Between suchsimulated steps, U' will keep the heads on the second and third tapes at theirleft ends, and the head of the first tape scanning the a of the encoded version ofthe symbol that M would be scanning at the corresponding time.U' simulates a step of M as follows: It scans its second tape until it findsa quadruple whose first component matches the encoded state written in itsthird tape, and whose second component matches the encoded symbol scannedin the first tape.
If it finds such a quadruple, it changes the state to the thirdcomponent of that quadruple, and performs in the first tape the action suggestedby the fourth component. If the fourth component encodes a symbol of the tapealphabet of M, this symbol is written in the first tape. If the fourth componentis aOj~210, the encoding of~, then [}' moves its first head to the first a symbolto the left, and if it is the encoding of -+, to the right. If a U is encountered, U'must convert it to aO j , the encoding of a blank of M.If at some step the state-symbol combination is not found in the second tape,this means that the state is a halting state. U' also halts at an appropriate state.This completes our description of the operation of U'.Problems for Section 5.25.2.1.(a)(b)(c)Recall the Turing machine M in Example 4.1.1What is the string "M"?What is the representation of the string aaa?Suppose that the universal (3-tape) Turing machine U' described in thischapter simulates the operation of M on input aaa.
What are the contentsof the tapes of U' at the beginning of the simulation? At the beginning ofthe simulation of the third step of M?5.2.2. By analogy to the universal Turing machine, we could hope to design auniversal finite automaton U that accepts the language {"AI" "w" : w EL(M)}. Explain why universal finite automata cannot exist.5.3: The Halting ProblemliiJ251THE HALTING PROBLEMSuppose that you have written a program, in your favorite programming language, that performs the following remarkable feat: It takes as input any program P, written in the same language, and an input X of that program.
Bysome clever analysis, your program always determines correctly whether the program P would halt on input X (it returns "yes" if it does), or whether it wouldrun forever (it returns "no"). You have named this program halts(P, X).This is a most valuable program. It discovers all sorts of subtle bugs thatmake other programs run forever on certain inputs. Using it you can achievemany remarkable things. Here is one somewhat subtle example: You can use itto write another program, with the ominous name diagonal(X) (recall the proofby diagonalization that 2N is not countable in Section 1.5):diagonal(X)a: if halts(X, X) then goto a else haltNotice what diagonal(X) does: If your halts program decides that programX would halt if presented with itself as input, then diagonal(X) loops forever;otherwise it halts.And now comes the unanswerable question: Does diagonal(diagonal) halt?It halts if and only if the call halts( diagonal.
diagonal) returns "no"; in otherwords, it halts if and only if it does not halt. This is a contradiction: we mustconclude that the only hypothesis that started us on this path is false, thatprogram halts(P, X) does not exist. That is to say, there can be no program, noalgorithm for solving the problem halts would solve: to tell whether arbitraryprograms would halt or loop.This kind of argument should be familiar not only from your past exposureto computer science, but also from general twentieth-century culture. The pointis that we have now introduced all the necessary machinery for presenting aformal, mathematically rigorous version of this paradox.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
