The Halting ProblemOverviewTuring MachinesParts of a TMTM Description 7 Tuple, M = (Q, , , , qo, B, qaccept)Limits to TMsIntro to the Halting ProblemCan a TM accept a TM as input? Example 1.Can a TM accept a TM as input? Example 2.Can a Program accept a Program as input? Example 3.“Given an arbitrary Turing Machine T as input and equally arbitrary tape t, decide whether T halts on t.”Construct a new machine TH’Construct a new machine TH’’Slide 14The Halting Problem is not possible in C .The Halting Problem is not possible in C.Difference between UTMs and the TM in the Halting Problem.QuestionsReferencesThe Halting ProblemThomas Dohaney2/7/08Overview•Review TMs•Parts of a TM•Description of a TM•Intro to Halting Problem•Can a TM accept a TM as input?•The Halting Problem Proof•The Halting Problem is not possible in C•UTMs and the TM in the Halting Problem•ReferencesTuring Machines•TMs finite, finite description.•Model computation, and sophisticated methods.•Theoretical model of a computing machine.•As powerful as any other computer device.•Has many properties…A1 A2 A3 An B…[Homer, Selman p23]Parts of a TM•Semi-infinite input tape, containing an input word (string).•Tape made of individual cells.•Cells hold a symbol from the tape alphabet .•Read-write head reads then prints a symbol.•Then head shifts one cell left or right.•TM changes state internally.A1 A2 A3 An B…[Homer, Selman p23]TM Description7 Tuple, M = (Q, , , , qo, B, qaccept)•Q [finite set of states]• [gamma, the tape alphabet]•B [the blank symbol, B ]• [sigma, the input alphabet]• [delta, the transition function]•qo[initial state, qo Q]•qaccept[accept state]•qreject[reject state][Homer, Selman p24]Limits to TMs•There are limits to the power of TMs.•A TM continues until it reaches accept state, or reject state where it will halt.•If it never reaches one, then it continues computing forever.•There exists problems that TMs cannot solve.•These problems contain no effective procedure and no recursive computation exists.•The problems unsolvable by TMs are also unsolvable by any equivalent formal programming systems.[Dewdney p391] [Homer, Selman p25]Intro to the Halting Problem•The best known problem that is unsolvable by a TM is the Halting Problem.•“Given an arbitrary Turing Machine T as input and equally arbitrary tape t, decide whether T halts on t.”•Basically TM that takes a TM, T as its input, and simulates the T running on input t, and returns or decides whether or not T halts on t.•Can a TM accept a TM as input? (important to understand)•3 Examples.[Dewdney p391]Can a TM accept a TM as input?Example 1.•Consider a Universal Turing Machine.•UTMs represent the set of all possible TMs, and all possible effective procedures.•UTMs take input in the form (dT, t). •UTMs mimics the action of an arbitrary TM, T by reading its description off the tape, and simulates its behavior on t.•Produces the same result as T.•Simple TMs can also take descriptionsof other TM as input.descrption of T input t B…[Dewdney p343, p392]Can a TM accept a TM as input?Example 2.•TMs can be encoded as words, (strings) for other TMs. •M = (Q, , , , qo, B, qaccept) 7-tuples, only 4 are important.•Represent finite set of states Q = {qo, q1, …} as a string in binary using unary conversion (n+1 ones represent n).•Represent alphabet, 0, 1, move left, move right as a string of different size blocks of ones.•Represent current state and next state transitions as a string using unary conversion.•Use 0s as delimiters between strings.•These 4 strings together make one string, the description of T.•Consider that programs can accept other programs as input.[Homer, Selman p43] [SEP]Can a Program accept a Program as input? Example 3.•Yes as a string, consider the valid C program.•The string of a valid C program input for another program.•Once compiled, this is translated to machine language, then translated to a string of 0s and 1s.[Greenlaw, Hoover p11]“Given an arbitrary Turing Machine T as input and equally arbitrary tape t, decide whether T halts on t.”•Formulate a proof, suppose such a machine does exist, call it TH. •Let t be input for T. •Let T be encoded as a description for TH.•If T accepts and halts on t,then TH will give an equivalent result and transfer to the halting“yes” state.•If T does not halt on t, then TH willtransfer to the halting “no” state.•If TH exists, then we can constructanother machine TH’ by modifyingTH.[Dewdney p392] dT t B…trueyes noq1Construct a new machine TH’•Add another machine Tc (or someextra code) that makes a copy ofdT and hands it to TH’s initialstate.•Alter TH so that it decides if T halts on dT rather than t.•TH‘s only job is to decide if T halts on dT.•If TH’ exists, then we can constructanother machine by modifyingTH’. dT B …trueyes noTCTH’dTq1[Dewdney p392-393]Construct a new machine TH’’•Alter TH’’s two halting transitions so that the yes and no state are diverted to two new states.•The yes transition goes fromq1 to qn, once in qn it will neverhalt (infinite loop).•The no transition goes fromq1 to qh a halting state. dT B …trueyes noTH’’dTq1qhqn[Dewdney p394]The Halting Problem•If TH’’ exists, then we can input its own description dTH’’.•Case 1: If TH’’ halts on dTH’’ , then TH’’ does not halt on dTH’’ because of an endless loop.•Case 2: If TH’’ does not halt on dTH’’ , then TH’’ does halt on dTH’’ .•This contradicts that TH ever existed in the first place.•The Halting Problem is not solvableby any TM. dTH’’ B trueyes nodTq1qhqn…[Dewdney p394]21The Halting Problem is not possible in C . [Greenlaw, Hoover p11]•Assume a Halts() function exists. Input the c program from earlier into the function.•Imagine the function Halts(program, input).•If Halts exists it is guaranteed to return.The Halting Problem is not possible in C.•Observe the new program in C. Save the program as diagonal.c•Run diagonal and add its own source code as input.•Halts(diagonal, diagonal) results in two cases.•Returns 0, then diagonalloops forever, but this can onlyhappen if Halts returns
View Full Document
Unlocking...