1610906232-7ba7dbaea13262b50a6029d682cb7f1b (824370), страница 40
Текст из файла (страница 40)
If it sees a U whilelooking for a 0, this means that the input number has a binary representationthat is all 1's (it is a power of two minus one), and so the machine again writes a1 in the place of the U and halts, after shifting the whole string one position tothe right. Strictly speaking, the machine shown does not compute n + 1 becauseit fails to always halt with its head to the left of the result; but this can befixed by adding a copy of Ru (Figure 4-5). <)Figure 4-12The last remark of the previous subsection, on our inability to tell whethera Turing machine decides a language, also applies to function computation.
Theprice we must pay for the very broad range of functions that Turing machinescan compute, is that we cannot tell whether a given Turing machine indeedcomputes such a function -that is to say, whether it halts on all inputs.198Chapter 4: TURING MACHINESRecursively Enumerable LanguagesIf a Turing machine decides a language or computes a function, it can be reasonably thought of as an algorithm that performs correctly and reliably somecomputational task. We next introduce a third, subtler, way in which a Turingmachine can define a language:Definition 4.2.4: Let M = (K,~, 5, s, H) be a Turing machine, let ~o <;;;~ - {U, ~} be an alphabet, and let L <;;; ~o be a language. We say that Msemi decides L if for any string w E ~o the following is true: w E L if and onlyif M halts on input w.
A language L is recursively enumerable if and onlyif there is a Turing machine M that semidecides L.Thus when M is presented with input w E L, it is required to halt eventually.We do not care precisely which halting configuration it reaches, as long as it doeseventually arrive at a halting configuration. If however w E ~o L, then Mmust never enter the halting state.
Since any configuration that is not haltingyields some other configuration (5 is a fully defined function), the machine mustin this case continue its computation indefinitely.Extending the "functional" notation of Turing machines that we introducedin the previous subsection (which allows us to write equations such as M (w) =v), we shall write M(w) =/ if M fails to halt on input w. In this notation,we can restate the definition of semi decision of a language L <;;; ~o by Turingmachine M as follows: For all w E ~o, M(w) =/ if and only if w ¢ L.-Example 4.2.4: Let L = {w E {a,b}* : w contains at least one a}. Then L issemi decided by the Turing machine shown in Figure 4-13.Figure 4-13This machine, when started in configuration (qO, ~jJl1J) for some w E {a, b}',simply scans right until an a is encountered and then halts. If no a is found,the machine goes on forever into the blanks that follow its input, never halting.So L is exactly the set of strings w in {a, b}' such that M halts on input w.Therefore M semidecides L, and thus L is recursively enumerable.O"Going on forever into the blanks" is only one of the ways in which a Turingmachine may fail to halt.
For example, any machine with 5(q,a) = (q,a) will"loop forever" in place if it ever encounters an a in state q. Naturally, morecomplex looping behaviors can be designed, with the machine going indefinitelythrough a finite number of different configurations.4.2: Computing with Turing Machines199The definition of semidecision by Turing machines is a rather straightforward extension of the notion of acceptance for the deterministic finite automaton.There is a major difference, however. A finite automaton always halts when ithas read all of its input -the question is whether it halts on a final or a non finalstate.
In this sense it is a useful computational device, an algorithm from whichwe can reliably obtain answers as to whether an input belongs in the acceptedlanguage: We wait until all of the input has been read, and we then observe thestate of the machine. In contrast, a Turing machine that semidecides a languageL cannot be usefully employed for telling whether a string w is in L, because,if w ~ L, then we will never know when we have waited enough for an answer. tTuring machines that semidecide languages are no algorithms.We know from Example 4.2.1 that {anbnc n : n ~ O} is a recursive language.But is it recursively enumerable? The answer is easy: Any recursive language isalso 1'ecursively enumerable.
All it takes in order to construct another Turing machine that semidecides, instead of decides, the language is to make the rejectingstate n a nonhalting state, from which the machine is guaranteed to never halt.Specifically, given any Turing machine M = (K,~, 5, s, {y, n}) that decides L, wecan define a machine M' that semidecides L as follows: M = (K,~,5',s,{y}),where 5' is just 5 augmented by the following transitions related to n -no longera halting state: 5' (n, a) = (n, a) for all a E ~.
It is clear that if M indeed decidesL, then ]I.,£' semidecides L, because M' accepts the same inputs as ]I.,f; furthermore, if ]I.,f rejects an input w, then M' does not halt on 'IV (it "loops forever" instate n). In other words, for all inputs w, M'(w) =/ if and only if M(w) = n.We have proved the following important result:Theorem 4.2.1: If a language is recursive, then it is recursively enumerable.Naturally, the interesting (and difficult) question is the opposite: Can wealways transform every Turing machine that semidecides a language (with ourone-sided definition of semidecision that makes it virtually useless as a computational device) into an actual algorithm for deciding the same language? We shallsee in the next chapter that the answer here is negative: There are recursivelyenumerable languages that are not recursive.An important property of the class of recursive languages is that it is closedunder complement:Theorem 4.2.2: If L is a recursive language, then its complement L is alsot We have already encountered the same difficulty with pushdown automata (recallSection 3.7).
A pushdown automaton can in principle reject an input by manipulating forever its stack without reading any further input -in Section 3.7 wehad to remove such behavior in order to obtain computationally useful pushdownautomata for certain context-free languages.200Chapter 4: TURING MACHINESrecursive.Proof: If L is decided by Turing machine M = (K,~, 5, s, {y, n}), then L isdecided by the Turing machine M' = (K,~, 5', s, {y, n}) which is identical to Mexcept that it reverses the roles of the two special halting states y and n. Thatis, 5' is defined as follows:5'(q,a) ={~5(q, a)if 5(q, a) = ]f,if 5(q, a) = n,otherwise.It is clear that M' (w) = y if and only if M (w) = n, and therefore M' decidesL .•Is the class of recursively enumerable languages also closed under complement? Again, we shall see in the next chapter that the answer is negative.Problems for Section 4.24.2.1. Give a Turing machine (in our abbreviated notation) that computes thefollowing function from strings in {a, b} * to strings in {a, b} *: f (w) = ww R .4.2.2.
Present Turing machines that decide the following languages over {a, b}:(a) 0(b) {e}(c) {a}(d) {a}*4.2.3. Give a Turing machine that semidecides the language a*ba*b.4.2.4. (a) Give an example of a Turing machine with one halting state that doesnot compute a function from strings to strings.(b) Give an example of a Turing machine with two halting states, y and n,that does not decide a language.(c) Can you give an example of a Turing machine with one halting statethat does not semidecide a language?BEXTENSIONS OF THE TURING MACHINEThe examples of the previous section make it clear that Turing machines canperform fairly powerful computations, albeit slowly and clumsily. In order tobetter understand their surprising power, we shall consider the effect of extendingthe Turing machine model in various directions.
We shall see that in each case2014.3: Extensions of the Turing Machinethe additional features do not add to the classes of computable functions ordecidable languages: the "new, improved models" of the Turing machine canin each instance be simulated by the standard model. Such results increase ourconfidence that the Turing machine is indeed the ultimate computational device,the end of our progression to more and more powerful automata. A side benefitof these results is that we shall feel free subsequently to use the additionalfeatures when designing Turing machines to solve particular problems, securein the knowledge that our dependency on such features can, if necessary, beeliminated.Multiple TapesOne can think of Turing machines that have several tapes (see Figure 4-14).Each tape is connected to the finite control by means of a read/write head (oneon each tape).
The machine can in one step read the symbols scanned by all itsheads and then, depending on those symbols and its current state, rewrite someof those scanned squares and move some of the heads to the left or right, inaddition to changing state. For any fixed integer k ~ 1, a k-tape Thring machineis a Turing machine equipped as above with k tapes and corresponding heads.Thus a "standard" Turing machine studied so far in this chapter is just a k-tapeTuring machine, with k = 1.Definition 4.3.1: Let k ~ 1 be an integer.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
