《9-Universality and uncomputability 2022-11-2 232314 16.pdf》由会员分享，可在线阅读，更多相关《9-Universality and uncomputability 2022-11-2 232314 16.pdf（34页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、9Universality and uncomputability“A function of a variable quantity is an analytic expression composed in anyway whatsoever of the variable quantity and numbers or constant quantities.”,Leonhard Euler,1748.“The importance of the universal machine is clear.We do not need to have aninfinity of differe
2、nt machines doing different jobs.The engineering problemof producing various machines for various jobs is replaced by the office work ofprogramming the universal machine”,Alan Turing,1948One of the most significant results we showed for Boolean circuits(or equivalently,straight-line programs)is the
3、notion of universality:there is a single circuit that can evaluate all other circuits.However,this result came with a significant caveat.To evaluate a circuit of gates,the universal circuit needed to use a number of gates largerthan.It turns out that uniform models such as Turing machines orNAND-TM
4、programs allow us to“break out of this cycle”and obtaina truly universal Turing machine that can evaluate all other machines,including machines that are more complex(e.g.,more states)than itself.(Similarly,there is a Universal NAND-TM program that canevaluate all NAND-TM programs,including programs
5、that have morelines than.)It is no exaggeration to say that the existence of such a universalprogram/machine underlies the information technology revolutionthat began in the latter half of the 20th century(and is still ongoing).Up to that point in history,people have produced various special-purpose
6、 calculating devices such as the abacus,the slide ruler,andmachines that compute various trigonometric series.But as Turing(who was perhaps the one to see most clearly the ramifications ofuniversality)observed,a general purpose computer is much more pow-erful.Once we build a device that can compute
7、the single universalfunction,we have the ability,via software,to extend it to do arbitrarycomputations.For example,if we want to simulate a new Turing ma-chine,we do not need to build a new physical machine,but ratherCompiled on 10.28.2022 19:47Learning Objectives:The universal machine/program-“onep
8、rogram to rule them all”A fundamental result in computer science andmathematics:the existence of uncomputablefunctions.The halting problem:the canonical example ofan uncomputable function.Introduction to the technique of reductions.Rices Theorem:A“meta tool”foruncomputability results,and a starting
9、pointfor much of the research on compilers,programming languages,and softwareverification.326introduction to theoretical computer sciencecan represent as a string(i.e.,using code)and then input to theuniversal machine.Beyond the practical applications,the existence of a universal algo-rithm also has
10、 surprising theoretical ramifications,and in particularcan be used to show the existence of uncomputable functions,upend-ing the intuitions of mathematicians over the centuries from Eulerto Hilbert.In this chapter we will prove the existence of the univer-sal program,and also show its implications f
11、or uncomputability,seeFig.9.1This chapter:A non-mathy overviewIn this chapter we will see two of the most important resultsin Computer Science:1.The existence of a universal Turing machine:a single algo-rithm that can evaluate all other algorithms,2.The existence of uncomputable functions:functions(
12、includ-ing the famous“Halting problem”)that cannot be computedby any algorithm.Along the way,we develop the technique of reductions as away to show hardness of computing a function.A reductiongives a way to compute a certain function using“wishfulthinking”and assuming that another function can be co
13、m-puted.Reductions are of course widely used in program-ming-we often obtain an algorithm for one task by usinganother task as a“black box”subroutine.However we willuse it in the“contra positive”:rather than using a reductionto show that the former task is“easy”,we use them to showthat the latter ta
14、sk is“hard”.Dont worry if you find thisconfusing-reductions are initially confusing-but they can bemastered with time and practice.9.1 UNIVERSALITY OR A META-CIRCULAR EVALUATORWe start by proving the existence of a universal Turing machine.This isa single Turing machine that can evaluate arbitrary T
15、uring machines on arbitrary inputs,including machines that can have morestates and larger alphabet than itself.In particular,can even beused to evaluate itself!This notion of self reference will appear time andagain in this book,and as we will see,leads to several counter-intuitivephenomena in compu
16、ting.universality and uncomputability327Figure 9.1:In this chapter we will show the existenceof a universal Turing machine and then use this to de-rive first the existence of some uncomputable function.We then use this to derive the uncomputability ofTurings famous“halting problem”(i.e.,the HALTfunc
17、tion),from which a host of other uncomputabil-ity results follow.We also introduce reductions,whichallow us to use the uncomputability of a function toderive the uncomputability of a new function.Figure 9.2:A Universal Turing Machine is a singleTuring Machine that can evaluate,given input the(descri
18、ption as a string of)arbitrary Turing machine and input,the output of on.In contrast tothe universal circuit depicted in Fig.5.6,the machine can be much more complex(e.g.,more states ortape alphabet symbols)than.Theorem 9.1 Universal Turing Machine.There exists a Turing machine such that on every st
19、ring which represents a Turing machine,and 0,1,(,)=().That is,if the machine halts on and outputs some 0,1then(,)=,and if does not halt on (i.e.,()=)then(,)=.Big Idea 11There is a“universal”algorithm that can evaluatearbitrary algorithms on arbitrary inputs.Proof Idea:Once you understand what the th
20、eorem says,it is not that hard toprove.The desired program is an interpreter for Turing machines.That is,gets a representation of the machine (think of it as sourcecode),and some input,and needs to simulate the execution of on.Think of how you would code in your favorite programminglanguage.First,yo
21、u would need to decide on some representationscheme for.For example,you can use an array or a dictionaryto encode s transition function.Then you would use some datastructure,such as a list,to store the contents of s tape.Now you cansimulate step by step,updating the data structure as you go along.Th
22、e interpreter will continue the simulation until the machine halts.Once you do that,translating this interpreter from your favoriteprogramming language to a Turing machine can be done just as wehave seen in Chapter 8.The end result is whats known as a“meta-328introduction to theoretical computer sci
23、encecircular evaluator”:an interpreter for a programming language in thesame one.This is a concept that has a long history in computer sciencestarting from the original universal Turing machine.See also Fig.9.3.9.1.1 Proving the existence of a universal Turing MachineTo prove(and even properly state
24、)Theorem 9.1,we need to fix somerepresentation for Turing machines as strings.One potential choicefor such a representation is to use the equivalence between Turingmachines and NAND-TM programs and hence represent a Turingmachine using the ASCII encoding of the source code of the corre-sponding NAND
25、-TM program.However,we will use a more directencoding.Definition 9.2 String representation of Turing Machine.Let be a Turingmachine with states and a size alphabet =0,1(weuse the convention 0=0,1=1,2=,3=).We represent as the triple(,)where is the table of values for:=(0,0),(0,1),(1,1),where each val
26、ue(,)is a triple(,)with,and a number 0,1,2,3 encoding one of L,R,S,H.Thussuch a machine is encoded by a list of 2+3 natural num-bers.The string representation of is obtained by concatenating aprefix free representation of all these integers.If a string 0,1does not represent a list of integers in the
27、 form above,then we treatit as representing the trivial Turing machine with one state thatimmediately halts on every input.RRemark 9.3 Take away points of representation.Thedetails of the representation scheme of Turing ma-chines as strings are immaterial for almost all applica-tions.What you need t
28、o remember are the followingpoints:1.We can represent every Turing machine as a string.2.Given the string representation of a Turing ma-chine and an input,we can simulate sexecution on the input.(This is the content ofTheorem 9.1.)An additional minor issue is that for convenience wemake the assumpti
29、on that every string represents someTuring machine.This is very easy to ensure by justmapping strings that would otherwise not represent auniversality and uncomputability329Turing machine into some fixed trivial machine.Thisassumption is not very important,but does make afew results(such as Rices Th
30、eorem:Theorem 9.15)alittle less cumbersome to state.Using this representation,we can formally prove Theorem 9.1.Proof of Theorem 9.1.We will only sketch the proof,giving the majorideas.First,we observe that we can easily write a Python programthat,on input a representation(,)of a Turing machine anda
31、n input,evaluates on.Here is the code of this program forconcreteness,though you can feel free to skip it if you are not familiarwith(or interested in)Python:#constantsdef EVAL(,x):Evaluate TM given by transition table on input xTape=+a for a in xi=0;s=0#i=head pos,s=statewhile True:s,Tapei,d=(s,Tap
32、ei)if d=H:breakif d=L:i=max(i-1,0)if d=R:i+=1if i=len(Tape):Tape.append()j=1;Y=#produce outputwhile Tapej!=:Y.append(Tapej)j+=1return YOn input a transition table this program will simulate the cor-responding machine step by step,at each point maintaining theinvariant that the arrayTapecontains the
33、contents of s tape,andthe variablescontains s current state.The above does not prove the theorem as stated,since we needto show a Turing machine that computes EVAL rather than a Pythonprogram.With enough effort,we can translate this Python codeline by line to a Turing machine.However,to prove the th
34、eorem wedont need to do this,but can use our“eat the cake and have it too”paradigm.That is,while we need to evaluate a Turing machine,inwriting the code for the interpreter we are allowed to use a richermodel such as NAND-RAM since it is equivalent in power to Turingmachines per Theorem 8.1.330intro
35、duction to theoretical computer scienceTranslating the above Python code to NAND-RAM is truly straight-forward.The only issue is that NAND-RAM doesnt have the dictio-nary data structure built in,which we have used above to store thetransition function.However,we can represent a dictionary ofthe form
36、 0 0,1 1 as simply a list of pairs.To compute we can scan over all the pairs until we find one ofthe form(,)in which case we return.Similarly we scan the listto update the dictionary with a new value,either modifying it or ap-pending the pair(,)at the end.RRemark 9.4 Efficiency of the simulation.The
37、 argu-ment in the proof of Theorem 9.1 is a very inefficientway to implement the dictionary data structure inpractice,but it suffices for the purpose of proving thetheorem.Reading and writing to a dictionary of values in this implementation takes()steps,butit is in fact possible to do this in(log)st
38、eps usinga search tree data structure or even(1)(for“typical”instances)using a hash table.NAND-RAM and RAMmachines correspond to the architecture of modernelectronic computers,and so we can implement hashtables and search trees in NAND-RAM just as they areimplemented in other programming languages.T
39、he construction above yields a universal Turing machine with avery large number of states.However,since universal Turing machineshave such a philosophical and technical importance,researchers haveattempted to find the smallest possible universal Turing machines,seeSection 9.7.9.1.2 Implications of u
40、niversality(discussion)There is more than one Turing machine that satisfies the condi-tions of Theorem 9.1,but the existence of even a single such machineis already extremely fundamental to both the theory and practice ofcomputer science.Theorem 9.1s impact reaches beyond the particu-lar model of Tu
41、ring machines.Because we can simulate every Turingmachine by a NAND-TM program and vice versa,Theorem 9.1 im-mediately implies there exists a universal NAND-TM program such that(,)=()for every NAND-TM program.We canalso“mix and match”models.For example since we can simulateevery NAND-RAM program by
42、a Turing machine,and every Turingmachine by the calculus,Theorem 9.1 implies that there exists a expression such that for every NAND-RAM program and input on which()=,if we encode(,)as a-expression (using theuniversality and uncomputability331Figure 9.3:a)A particularly elegant example of a“meta-cir
43、cular evaluator”comes from John Mc-Carthys 1960 paper,where he defined the Lispprogramming language and gave a Lisp function thatevaluates an arbitrary Lisp program(see above).Lispwas not initially intended as a practical program-ming language and this example was merely meantas an illustration that
44、 the Lisp universal function ismore elegant than the universal Turing machine.Itwas McCarthys graduate student Steve Russell whosuggested that it can be implemented.As McCarthylater recalled,“I said to him,ho,ho,youre confusingtheory with practice,this eval is intended for reading,notfor computing.B
45、ut he went ahead and did it.That is,hecompiled the eval in my paper into IBM 704 machine code,fixing a bug,and then advertised this as a Lisp interpreter,which it certainly was”.b)A self-replicating C programfrom the classic essay of Thompson Tho84.-calculus encoding of strings as lists of 0s and 1s
46、)then()eval-uates to an encoding of.More generally we can say that for every and in the set Turing machines,RAM Machines,NAND-TM,NAND-RAM,-calculus,JavaScript,Python,of Turing equivalentmodels,there exists a program/machine in that computes the map(,)()for every program/machine .The idea of a“univer
47、sal program”is of course not limited to theory.For example compilers for programming languages are often used tocompile themselves,as well as programs more complicated than thecompiler.(An extreme example of this is Fabrice Bellards ObfuscatedTiny C Compiler which is a C program of 2048 bytes that c
48、an compilea large subset of the C programming language,and in particular cancompile itself.)This is also related to the fact that it is possible to writea program that can print its own source code,see Fig.9.3.There areuniversal Turing machines known that require a very small numberof states or alph
49、abet symbols,and in particular there is a universalTuring machine(with respect to a particular choice of representingTuring machines as strings)whose tape alphabet is,0,1 andhas fewer than 25 states(see Section 9.7).9.2 IS EVERY FUNCTION COMPUTABLE?In Theorem 4.12,we saw that NAND-CIRC programs can
50、computeevery finite function 0,1 0,1.Therefore a natural guess isthat NAND-TM programs(or equivalently,Turing machines)couldcompute every infinite function 0,1 0,1.However,thisturns out to be false.That is,there exists a function 0,1 0,1that is uncomputable!332introduction to theoretical computer sc