1610906232-7ba7dbaea13262b50a6029d682cb7f1b (824370), страница 51
Текст из файла (страница 51)
Hennie1977.The following are other advanced books on Turing machines and related concepts introduced in this and the three subsequent chapters:o M. Davis, ed., The Undecidable, Hewlett, N.Y.: Raven Press, 1965. (This bookcontains many original articles on several aspects of the subject, including thepapers of Turing and Post cited above.)o M. Davis, ed.,Computability and Unsolvability New York: McGraw-Hill, 1958.o S.
C. Kleene,trand, 1952,Introduction to Metamathematics, Princeton, N.J.: D. Van Nos-o W. S. Brainerd and L. H. Landweber,Wiley, 1974,Theory of Computation, New York: JohnChapter 4: TURING MACHINES244o M. Machtey and P. R. Young,An Introduction to the General Theory of Algorithms, New York: Elsevier North-Holland, 1978,oH. Rogers, Jr.,The Theory of Recursive Functions and Effective Computability,New York: McGraw-Hill, 1967,o M. Sipser,Introduction to the Theory of Computation, Boston, Mass.: PWSPublishers, 1996,D. Ullman Introduction to Automata Theory, Languages,and Computation, Reading, Mass.: Addison Wesley, 1979.o J.
E. Hopcroft and J.o C. H. PapadimitriouComputational Complexity, Reading, Mass.: Addison Wes-ley, 1994.H. Hermes, Enumerability, Decidability, Computability, New York: SpringerVerlag, 1969 (translated from the German edition, 1965).Our notion and notation for combining Turing machines (Section 4.3) was influencedby this last book.Random access machines, similar in spirit to our "random access Turing machines"in Section 2.4, were studied inoo S.
A. Cook and R. A. Reckhow"Time-bounded random-access machines," Journal of Computer and Systems Sciences, 7, 4, pp. 354-375, 1973.Primitive and p,-recursive functions are due to Kleeneo S. C. Kleene"General recursive functions of natural numbers," MathematischeAnnalen, 112, pp. 727-742, 1936,and Markov Algorithms (Problem 2.6.5) are fromo A. A. Markov Theory of Algorithms, Trudy Math.
Inst. V. A.Steklova, 1954.English translation: Israel Program for Scientific Translations, Jerusalem, 1961.Undecidability5.1 THE CHURCH-TURING THESISIn this book we address this question: What can be computed? (And, more intriguingly, what. cannot be computed?) We have introduced various and diversemathematical models of computational processes that accomplish concrete computational tasks -in particular, decide, semidecide, or generate languages, andcompute functions. In the previous chapter we saw that Turing machines cancarry out surprisingly complex tasks of this sort. We have also seen that certainadditional features that we might consider adding to the basic Turing machinemodel, including a random access capability, do not increase the set of tasksthat can be accomplished.
Also, following a completely different path (namely,trying to generalize context-free grammars), we arrived at a class of languagegenerators with precisely the same power as Turing machines. Finally, by trying to formalize our intuitions on which numerical functions can be consideredcomputable, we defined a class of functions that turned out to be precisely therecursive ones.All this suggests that we have reached a natural upper limit on what acomputational device can be designed to do; that our search for the ultimateand most general mathematical notion of a computational process, of an algorithm, has been concluded successfully -and the Turing machine is the rightanswer. However, we have also seen in the last chapter t.hat not all Turing machines deserve to be called "algorithms:" We argued that Turing machines thatsemi decide languages, and thus reject by never halting, are not useful computational devices, whereas Turing machines that decide languages and computefunctions (and therefore halt at all inputs) are.
Our notion of an algorithm must245246Chapter 5: UNDECIDABILITYexclude Thring machines that may lIot halt on some inputs.We therefore propose to adopt the Turing machine that halts on all inputsas the precise formal notion corresponding to the intuitive notion of an "algorithm." Nothing will be considered an algorithm if it cannot be rendered as aThring machine that is guaranteed to halt on all inputs, and all such machineswill be rightfully called algorithms. This principle is known as the ChurchTuring thesis. It is a thesis, not a theorem, because it is not a mathematicalresult: It simply asserts that a certain informal concept (algorithm) correspondsto a certain mathematical object (Turing machine). Not being a mathematicalstatement, the Church-Thring thesis cannot be proved.
It is theoretically possible, however, that the Church-Turing thesis could be disproved at some futuredate, if someone were to propose an alternative model of computation that waspublicly acceptable as a plausible and reasonable model of computation, and yetwas provably capable of carrying out computations that cannot be carried outby any Thring machine. No one considers this likely.Adopting a precise mathematical notion of an algorithm opens up the intriguing possibility of formally proving that certain computational problems cannot be solved by any algorithm.
We already know enough to expect this. InChapter 1 we argued that if strings are used to represent languages, not every language can be represented: there are only a countable number of stringsover an alphabet, and there are uncountably many languages. Finite automata,pushdown automata, context-free grammars, unrestricted grammars, and Thring machines are all examples of finite objects that can be used for specifyinglanguages, and that can be themselves described by strings (in the next sectionwe develop in detail a particular way of representing Turing machines as strings).Accordingly, there are only countably many recursive and recursively enumerable languages over any alphabet. So although we have worked hard to extendthe capabilities of computing machines as far as possible, in absolute terms theycan be used for semideciding or deciding only an infinitesimal fraction of all thepossible languages.Using cardinality arguments to establish the limitation of our approach istrivial; finding particular examples of computational tasks that cannot be accomplished within a model is much more interesting and rewarding.
In earlierchapters we did succeed in finding certain languages that are not regular orcontext-free; in this chapter we do the same for the recursive languages. Thereare two major differences, however. First, these new negative results are notjust temporary setbacks, to be remedied in a later chapter where an even morepowerful computational device will be defined: according to the Church-Thringthesis, computational tasks that cannot be performed by Turing machines areimpossible, hopeless, undecidable.
Second, our methods for proving that languages are not recursive will have to be different from the "pumping" theoremswe used for exploiting the weaknesses of context-free grammars and finite au-5.2: Universal Turing Machines247tomata. Rather, we must devise techniques for exploiting the considerable powerof Turing machines in order to expose their limitations. The aspect of the powerof Turing machines that we will explore is a kind of introspective ability theypossess: We point out that Turing machines can receive encodings of Turingmachines as inputs, and manipulate these encodings in interesting ways.
Wewill then ask what happens when a Turing machine manipulates an encodingof itself -an ingenious yet simple application of the diagonalization principle.How to encode a Turing machine so it can be manipulated by another (or thesame!) Turing machine is thus our next subject.liiJUNIVERSAL TURING MACHINESIs hardware or software the basis of computation? You may have an opinionon the matter -and on whether the question is meaningful and productive.But the fact is that the formalism for algorithms we introduced and developedin the last chapter -the Turing machipe- is an "un programmable" piece ofhardware, specialized at solving one particular problem, with instructions thatare "hard-wired at the factory."We shall now take the opposite point of view.
We shall argue that Turing machines are also software. That is, we shall show that there is a certain"generic" Turing machine that can be programmed, about the same way thata general-purpose computer can, to solve any problem that can be solved byTuring machines. The "program" that makes this generic machine behave like aspecific machine M will have to be a description of M. In other words, we shallbe thinking of the formalism of Turing machines as a programming language, inwhich we Celli write programs. Programs written in this language can then beinterpreted by a universal Turing machine -that is to say, another program inthe same language. That a program written in a language can interpret anyprogram in the same language is not a very novel idea -it is the basis of theclassical method for "bootstrapping" language processors.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
