We use optional third-party analytics cookies to understand how you use GitHub. You may use the International Edition, but it numbers a few of the problems differently.
Learn more. This is just one of the solutions for If nothing happens, download Xcode and try again. Reload to refresh your session. There are many alternatives to compile LaTeX files, such as: This branch is even with ryandougherty:master. The last remaining vampires yielded and fled as Crow came screaming into the clearing. Crow staggered toward Val and she cried out his name and ran to him, wrapping her arms around him, weeping and saying his name over and over again as they both collapsed down to their knees.
Then he also slumped to his knees, looked blankly at Val and Crow, and fell forward onto the bloody hands that still held the sword. Sipser homework solutions Page and Sipser 3. Reading assignment: Sipser, Chapter 7. If either v or y has a. Poe, Roy W. That lab report you did for me was one of the how to write a qualitative methodology best in class. This is for exercise only. Class Notes Policy No need to wait for office hours or assignments to be graded to find out where you took a wrong turn.
Emphasizing Search Problems. The best way to find the solutions is of course to solve the problems yourself; just reading the solutions somewhere is pretty useless for anything you might want to do, other than getting a high grade on a problem set. For students viewing a recorded lecture, an alternate timed and graded those problems you wish to be counted as late. We read all comments about how to improve the course. We provide you with a clear access platform, For any company, it is necessary that they present their company in front of the public as a brand so, If you wish to grow your enterprise, you want to invest and make cash every time for marketing.
Associate Dean Kathleen Monagle at and 46 hours of the original live lecture. Computation, Third Edition submit all requests online at elizabethsid. Introduction to the Theory of Computation,. Recent introduction to the theory of computation 3rd edition pdf github Below is the list of theory of computation book recommended by the top university in India.
Share :. An equivalent essentially noncontracting grammar GL with a nonrecursive start symbol is constructed following the steps given in the proof of Theorem 4. Following the technique of Example 4.
For each variable, Algorithm 4. An equivalent grammar GU without useless symbols is constructed in two steps. The first step involves the construction of a grammar GT that contains only variables that derive terminal strings. Algorithm 4. The transformation of a grammar G from Chomsky normal form to Greibach normal form is accomplished in two phases.
In the first phase, the variables of the grammar are numbered and an intermediate grammar is constructed in which the first symbol of the right-hand side of every rule is either a terminal or a variable with a higher number than the number of the variable on the left-hand side of the rule. This is done by removing direct left recursion and by applying the rule replacement schema of Lemma 4. The variables S, A, B, and C are numbered 1, 2, 3, and 4 respectively.
The S rules are already in the proper form. Working backwards from the C rules and applying Lemma 4. We begin by showing how to reduce the length of strings on the right-hand side of the rules of a grammar in Greibach normal form. If a rule already has the desired form, no change is necessary. There are three cases to consider in creating the new rules. The process must be repeated until rules have been created for each variable created by the rule transformations. The construction in case 3 requires the original rule to have at least three variables.
This length reduction process can be repeated until each rule has a right-hand side of length at most 3. A detailed proof that this construction produces an equivalent grammar can be found in Harrison1.
Therefore, the strings abaa, bababa, and bbbaa are in L M. The proof is by induction on length of the input string. Any deviation from the prescribed order causes the computation to enter q3 and reject the string. States q1 or q3 are entered upon processing a single a. The state q3 represents the combination of the two conditions required for acceptance. Upon reading a second a, the computation enters the nonaccepting state q4 and rejects the string.
The states of the machine are used to count the number of symbols processed since an a has been read or since the beginning of the string, whichever is smaller. If an input string has a substring of length four without an a, the computation enters q4 and rejects the string. All other strings accepted. The DFA to accept this language differs from the machine in Exercise 20 by requiring every fourth symbol to be an a.
The first a may occur at position 1, 2, 3, or 4. If the string varies from this pattern, the computation enters state q8 and rejects the input. After arriving at q2 there are two ways to leave and return, taking the cycle q0 , q1 , q2 or the cycle q1 , q2. If q1 is entered upon processing the third to the last symbol, the computation accepts the input. A computation that enters q1 in any other manner terminates unsuccessfully.
Algorithm 5. The transition table of M is given in the solution to Exercise The nodes of the equivalent NFA are constructed in step 2 of Algorithm 5. The generation of Q0 is traced in the table below. The set Y consists of the states that may be entered upon processing an a from a state in X. However, this equality follows from the result in Exercise Chapter 6 Properties of Regular Languages 2. The node deletion algorithm must be employed individu- ally for each accepting state.
The language of M is the union of the strings accepted by q0 and q2. Without loss of generality, we may assume that G does not contain useless symbols. The algorithm to remove useless symbols, presented in Section 4. Thus the equivalent grammar obtained by this transformation is also regular. Intuitively but not precisely , the state qi represents the number of transitions from the start state when processing a string and the set X consists of states that require the same number of transitions to reach an accepting state.
The start state of the machine is the ordered pair [q0 , F]. If it is not already in Q0 , the ordered pair [qi a , Y] is added to the states of M0. The process is repeated until a transition is defined for each state-symbol pair. Back to the intuition, this occurs when the number of transitions from the start state is the same as the number of transitions needed to reach an accepting state. That is, when half of a string in L has been processed.
Then ui vi is the palindrome ai bbai. We conclude, by Corollary 6. There are three cases to consider. Case 2: v has one b. In this case, v contains a substring bat b. Pumping v produces two substrings of the form bat b in uv 2 w. By Theorem 6.
We begin by showing that these set operations are preserved by homomorphisms. Let x be an element of h XY. To establish the opposite inclusion, let x be an element in h X h Y. The other two set equalities can be established by similar arguments. We will use the recursive definition of regular sets to show that h X is regular whenever X is. The proof is by induction on the number of applications of the recursive step in Definition 2. Inductive hypothesis: Now assume that the homomorphic image of every regular set definable using n or fewer applications of the recursive step is regular.
By the inductive hypothesis, h Y and h Z are regular. Let G and G0 be corresponding regular and left-regular grammars. The proof is by induction on the length of the derivations. By the preceding lemma, the corresponding regular grammar G generates LR. Thus every language generated by a left-regular grammar is regular.
If L is a regular language, then so is LR. This implies that there is a regular grammar G that generates LR. The equivalence classes of the DFA in Example 5. By the argument in Theorem 6. Processing an a pushes A onto the stack. Strings of the form ai are accepted in state q1. The transitions in q1 empty the stack after the input has been read. A computation with input ai bj enters state q2 upon processing the first b.
Thus strings with either of these forms are rejected. A computation begins by pushing a C onto the stack, which serves as a bottom-marker throughout the computation. When an a is read with an A or C on the top of the stack, an A is pushed onto the stack.
This is accomplished by the transition to q2. If a B is on the top of the stack, the stack is popped removing one b. Processing a b with an A on the stack pops the A. The lone accepting state of the automaton is q5. The states q2 and q3 are the accepting states of M. The null string is accepted in q3. A computation of M0 with input w begins by putting C on the stack and entering q0.
The stack symbol C acts as a marker designating the bottom of the stack. From q0 , M0 continues with a computation identical to that of M with input w. We must also guarantee that the any string w accepted by M0 by final state is accepted by M by final state and empty stack.
We will outline the construction of a context- free grammar that generates L M. The steps follow precisely those given in Theorem 7. These rules transform a transition of M that does not remove an element from the stack into one that initially pops the stack and later replaces the same symbol on the top of the stack. The alphabet of G is the input alphabet of M0.
The variable hqi , A, qj i represents a computation that begins in state qi , ends in qj , and removes the symbol A from the stack. The rules of G are constructed as follows: 1. A derivation begins with a rule of type 1 whose right-hand side represents a computation that begins in state q0 , ends in a final state, and terminates with an empty stack, in other words, a successful computation in M0.
Rules of types 2 and 3 trace the action of the machine. Rules of type 4 are used to terminate derivations. The proof that the rules generate L M follows the same strategy as Theorem 7. Lemmas 7. To show that the assumption that L is context-free produces a contradiction, we examine all possible decompositions of z that satisfy the conditions of the pumping lemma.
By ii , one or both of v and x must be nonnull. That is, v occurs in z in a position of the form. In this case, v contains a substring ban b. Pumping v produces a string with two substrings of the form ban b. No string with this property is in L. Case 3: v has one b. Then v can be written ai baj and occurs in z as. Pumping v produces the substring. Regardless of its makeup, pumping any nonnull substring v of z produces a string that is not in the language L.
A similar argument shows that pumping x produces a string not in L whenever x is nonnull. Since one of v or x is nonnull, there is no decomposition of z that satisfies the requirements of the pumping lemma and we conclude that the language is not context-free.
Because of the restriction on its length, the substring vwx must have the form ai , bi , ci , ai bj , or bi cj. Pumping z produces the string uv 2 wx2 y. This operation increases the number of at least one, possibly two, but not all three types of terminals in z. Let z be any string of length 2 or more in L. That is, z must contain the substring ab or the substring ba.
Let L be a linear language. Let r by the number of variables of G and t be the maximum number of terminal symbols on the right-hand of any rule.
Since the sentential form uvAxy is generated by at most r rule applications, the string uvxy must have length less than k as desired. The variables, alphabet, and start symbol of G0 are the same as those of G. Induction on the length of derivations is used to show that a string u is a sentential form of G if, and only if, uR is a sentential form of G0.
We consider sentential forms of G generated by leftmost derivations and of G0 by rightmost derivations. Basis: The basis consists of sentential forms produced by derivations of length one. Inductive hypothesis: Assume that u is a sentential form of G derivable by n or fewer rule applications if, and only if, uR is a sentential form of G0 derivable by n or fewer rule applications. By the inductive hypothesis, y R AxR is a sentential form of G0 derivable by n rule applications.
In a like manner, we can prove that the reversal of every sentential form derivable in G 0 is derivable in G. The grammar G0 generates era L. The proof follows from a straightforward examination of the derivations of G and G 0. Conversely, let u be any string in L G0. The rules of G0 are obtained from those of G by substitution. See the solution to Exercise 27 for an explanation of the notation.
To show that h L is context-free, it suffices to show that it is generated by the grammar G0. The image of this mapping, which is context-free by part a , is era L. In Example 7. Chapter 8 Turing Machines 1. If the input is the null string, the computation halts in state qf with the tape head in position zero as desired. Otherwise, an a is moved to the right by transitions to states q 2 and q3.
Similarly, states q4 and q3 shift a b. This process is repeated until the entire string has been shifted. The strategy employed by the machine is i. Mark tape position 0 with a. If the input string is not empty, change the first symbol to X or Y to record if it was an a or b, respectively. Move to the end of the string and use strategy from the machine in part a to move the unmarked input on square to the right. Otherwise, repeat the process on the unmarked string. Shifting a string one square to the right is accomplished by states q3 to q7.
The arc from q4 to q8 when the shift has been completed. If another shift is needed, the entire process is repeated by entering q 1. The tape head is then returned to position zero and a search is initiated for a corresponding b. If a b is encountered in state q3 , an X is written and the tape head is repositioned to repeat the cycle q1 , q2 , q3 , q4. If no matching b is found, the computation halts in state q3 rejecting the input. We refer to the method of acceptance defined in the problem as acceptance by entering.
We show that the languages accepted by entering are precisely those accepted by final state, that is, the recursively enumerable languages. Computations of M0 are identical to those of M until M0 enters an accepting state. When this occurs, M0 halts accepting the input. A computation of M that enters an accepting state halts in that state in M0. A computation of M may enter and leave accepting states prior to termination; the intermediate states have no bearing on the acceptance of the input.
We construct a machine M0 that accepts L M by entering. A computation of M that accepts an input string halts in an accepting state q i. The corre- sponding computation of M0 reaches qi and then enters qf , the sole accepting state of M0. Clearly, every recursively enumerable language is accepted by a Turing machine in which stationary transitions are permitted.
A standard Turing machine can be considered to be such a machine whose transition function does not include any stationary transitions. We construct a standard Turing machine M0 that accepts L M. A transition of M that designates a movement of the tape head generates an identical transition of M0. The first transition prints a y, moves right and enters a new state. Regardless of the symbol being scanned, the subsequent transition moves left to the original position and enters qj.
We will build a context- sensitive Turing machine M0 that accepts L M. Intuitively, a computation of M0 ignores the second input symbol in the transition. The computation of the standard machine should read the x in state qi , determine the symbol on the right, and rewrite the original position accordingly. If the context- sensitive transition is not applicable, the sequence of standard transitions will check the symbol to the right and halt in state qi.
Part b provides the opposite inclusion; given a context- sensitive machine we can build a standard machine that accepts the same language. Thus the family of languages accepted by these types of machines are identical. The input is copied onto tape 1 in state q 1. State q2 returns the head reading tape 1 to the initial position.
With tape head 1 moving left-to-right and head 2 moving right-to-left, the strings on the two tapes are compared. If both heads simultaneously read a blank, the computation terminates in q 4. The maximal number of transitions of a computation with an input string of length n occurs when the string is accepted. Tape head 1 reads right-to-left, left-to-right, and then right-to-left through the input.
The computation of a string that is not accepted halts when the first mismatch of symbols on tape 1 and tape 2 is discovered. States p 0 to p7 nondeterministically select a substring of length three or more from the input. The accepting states of the composite machine are the accepting states of M.
This problem illustrates the two important features in the design of Turing machines. The first is the ability to use existing machines as components in more complex computations. The machine constructed in Exercise 5 c provides the evaluation of a single substring needed in this computation.
The flexibility and computational power that can be achieved by combining submachines will be thoroughly examined in Chapter 9. The second feature is the ability of a nondeterministic design to remove the need for the consideration of all possible substrings. If not, another substring is is generated and examined. This process must be repeated until an acceptable substring is found or all substrings have been generated and evaluated.
A nondeterministic transition to state q2 represents a guess that the current position of the head on tape 1 is the beginning of the second half of the string. The head on tape 2 is repositioned at the leftmost square in state q2. The remainder of the string on tape 1 is then compared with the initial segment that was copied onto tape 2. If a blank is read simultaneously on these tapes, the string is accepted.
Finding any mismatch between the tapes in this comparison causes the computation to halt without accepting the input. The maximal number of transitions occurs when all but the final symbol of the input string is copied onto tape 2. In this case, the head on tape 2 moves to tape position n, back to position 0, and begins the comparison. Let M be a nondeterministic Turing machine that halts for all inputs.
The technique in- troduced in the construction of an equivalent deterministic machine M0 given in Section 9. M0 systematically simulates all computa- tions of M, beginning with computations of length 0, length 1, length 2, etc. The simulation of a computation of M is guided by a sequence of numbers that are generated on tape 3. When one of the simulated computations accepts the input string, M0 halts and accepts.
If the input is not in L M , M0 indefinitely continues the cycle of generating a sequence of numbers on tape 3 and simulating the computation of M associated with that sequence. Unfortunately, the preceding approach cannot be used to show that L is recursive since the computation of M0 will never terminate for a string that is not in the language. To show that L M is recursive, we must construct a deterministic machine that halts for all inputs.
This can be accomplished by adding a fourth tape to M0 that records the length of the longest simulated computation that has not halted prematurely. A computation terminates prematurely if the simulation terminates before executing all of the transitions indicated by the sequence on tape 3. Upon the termination of a simulated computation that did not halt prematurely, the length of the sequence on tape 3 is recorded on tape 4.
The machine M0 checks the length of non-prematurely terminating computations of M prior to simulating a subsequent computation of M. If not, M0 halts and rejects. Otherwise, M0 simulates the next computation. If a string u is in L M , the computation of M0 will simulate an accepting computation of M and accept u. If u in not in L M , then all computations of M will terminate. Let k be the length of the longest computation of M with input u. Thus L is not only recursively enumerable, but also recursive.
Conversely, we must show that L is recursive when both L and its complement are recursively enumerable. By Theorem 8. These machines provide sufficient information to decide whether a string u is in L. We construct a two-tape machine M that simulates the computations of both M 1 and M2. A computation begins by copying the input onto tape 2 and repositioning the tape heads at the initial position.
This is accomplished by the transitions defined in i through v below. The status of the computation of M2 is unaffected by such a transition. For every input string, either the computation of M1 or M2 terminates. A string is accepted if the computation halts due to the lack of a transition for a configuration on tape 1. Thus the set of final states of M consists of triples of the form [qi , pj , 1].
The machine in Figure 8. Intuitively, the strings are generated on tape 2 and then output on tape 1. A is written on tape 1 followed by the string in the input position on tape 2.
For the remainder of the cycle, the tape head on tape 1 remains stationary while the next string is generated on tape 2. We will outline the strategy employed by a Turing machine that enumerates all ordered pairs of natural numbers. The enumerating machine has three tapes: the enumeration tape, the diagonal tape, and the work tape. The computation consists of an initialization phase followed by a loop that enumerates the ordered pairs. Initialization: 1.
The initialization writes the ordered pair [0, 0] on enumerating tape. All the elements in the square bounded by [0, 0] and [n, n] have already been written on the enumerating tape. Loop: 1. While the work tape is not blank - the string on the work is copied tape to the enumeration tape, - B is written on the enumeration tape, - the string on the diagonal tape is copied to the enumeration tape, - is written on the enumeration tape, - a 1 is erased from the work tape.
While the work tape is not blank - the string on the diagonal is copied tape to the enumeration tape, - B is written on the enumeration tape, - the string on the work tape is copied to the enumeration tape, - is written on the enumeration tape, - a 1 is erased from the work tape. Definition 8. After completely listing the strings in a finite language, an enumerating machine may continue indefinitely.
For a string not in the language that is lexicographically greater than any string in the language, the halting condition given in Case 2 of Theorem 8. Chapter 9 Turing Computable Functions 2.
Let M a machine that computes the partial characteristic function of a language L. A machine M0 that accepts L can be built by extending M. When a computation of M halts, M 0 - checks to see if 1 is on the tape, - if so, M0 enters an accepting state and halts, otherwise - M0 enters a rejecting state and halts. The input string represents an even number if a blank is read in q2 and an odd number if a blank is read in q3.
Tracing the computation of M with input n illustrates the interaction among the machines that make up M. The underscore indicates the position of the tape head in the configuration. This, in turn, causes the entire function to be undefined. Modifying h by defining h n to be 0 for all odd n produces a pair of functions g and h that provide a solution to Exercise 11 a. Let f be a Turing computable function and F a machine that computes f. A working copy of 0 is made and F is run on the copy.
The BRN macro is used to determine whether the computed value of f is 0. If not, the computed value is erased, the counter is incremented, and the subsequent f value is computed. If f never assumes the value 0, the computation continues indefinitely. Let R be a Turing computable unary relation and M a machine that computes the characteristic function of R.
A machine that accepts R can be built using M and the branch macro. Consequently, the composite machine accepts R. To show that R is computable, we build a machine M0 that writes the correct answer on the tape at the end of a computation of M.
The process is not quite as simple as it sounds, since M 0 must erase the tape prior to writing the answer. That means, M0 must record the furthest right on the tape reached during a computation of M. At this point it writes the new endmarker [R, B] on the tape and enters qj to continue the simiulation of M.
A similar set of transitions write a negative answer when M halts in a nonaccepting state. By Theorem 9. Diagonalization can be used to show that there are uncountably many functions that are the identity on the set of even natural numbers. Assume that this set of functions is countably infinite. Countability implies that there is an exhaustive listing f0 , f1 ,. This contradicts the assumption that the set is countably infinite. Since the set Turing computable functions is countable and the set of number-theoretic func- tions that are the identity on the even natural numbers is uncountable, there functions of the latter form that are uncomputable.
Chapter 10 The Chomsky Hierarchy 1. Repeated applications of the P and Q rules produce ai Ai bj Ebj. The derivation of aabaab demonstrates the repositioning of the variable A and its transformation to the terminal a. Let us first recall the proof of Theorem 7. Unfortunately, we must be careful in combining unrestricted grammars in this manner since the left-hand side of a rule may contain more than one symbol.
The grammars G1 and G2 must be constructed to insure that no rule can overlap the strings derived from S1 and S2. Using Exercise 3, we can assume that the left-hand side of every rule in G1 and G2 consists solely of variables. As before, we also assume that V1 and V2 are disjoint. Even though the pumping lemma is satiafied, L is nevertheless not context-free. The S rule puts a c on the end of the string. The construction of P is divided into two cases. This procedure can be repeated until the length of the right-hand of each rule is at most two.
The answer depends on the depth of the tree T. If the depth is 0, the language consists only of the null string, which is regular. This follows since the most steps down the tree that can be taken from the root is one, either right or left, followed by a move up the tree.
This process can be repeated any number of times to produce a string in L. In general, a string is accepted if it satisfies the following two conditions: a the number of steps that move down tree equals the number of steps that move up, snd b the steps do not specify a move down from a leaf or up from the root.
If the string represents a path the would leave the tree, the DFA enters an error state qe and rejects the string. This sequence can be used with Corollary 6. Whenever an L or R is read, a A is pushed onto the stack. When a U is read, if there is an A on the stack it is popped. Otherwise, the computation rejects the string. A string is accepted if the computation processes the entire string and halts with an empty stack. If so, then the final c is erased and the input shifted one position to the right producing hBwcj i.
The tape head is then moved to position 1 to read the blank preceding the input string. For the remainder of the computation, the transitions of M 0 are identical to those of M except M0 treats the c as a blank. Let k be the furthest tape position scanned during the computation of M that accepts a string w. Consequently M0 accepts wci. In this solution we represent the natural number n by 1 n.
The numbers 20 , 21 , 22 ,. Tape 3 is used in the generation of the sequence on tape 2. The computation of the machine with input u consists of the following actions. A 1 is written on tapes 2 and 3. Reading left to right, the length of the strings on tapes 1 and 2 is compared. If blanks are simultaneously read on tapes 1 and 2, the computation halts accepting the input. If a blank is read on tape 1 and a 1 on tape 2, the computation halts rejecting the input.
If a blank is read on tape 2 and a 1 on tape 1, then - the string on tape 3 is concatenated to the string on to tape 2, - tape 3 is erased and the string from tape 2 is copied to tape 3, - all tape heads are repositioned at the initial position, and - the computation continues with step 2. At the beginning of step 2, tapes 2 and 3 both contain the representation of 2 i.
The symbol assigned number n is encoded by the string 1 n. The encoding of a variable A and a terminal a will be denoted en A and en a. Rules are separated by The representation of a regular grammar G, denoted R G , is the concatenation of the encod- ing of the rules.
A computation of M that decides whether a string w is in L G begins with input consisting of the encoding of the rules of the grammar followed by and the encoding of w. The actions of a machine M that solves the derivability problem are described below. M uses the representation of the rules of G to simulate a derivation of G on tape 2.
The computation of M begins by determining whether the input has the form R G en w. If not, M halts rejecting the input. The encoding of S is written in position one of tape 2.
Let uA be the string that is encoded on tape 2. The encoding of the variable A is then replaced with the encoding of v on tape 2. If v is a terminal symbol or the null string, the string on tape 2 is compared with the encoding of w on tape 1. If they are identical, M halts and accepts the input. If not, steps 3—5 are repeated. Consequently, all computations of M terminate and M solves the derivability problem.
The appropriate action is determined by the form of input string. U 1 accepts by final state and has a single accepting state. A computation of U1 initially determines whether the input has the form R M w. If so, the computation continues with the simulation of the transitions of M in the manner of the uni- versal machine.
Before the simulation of a transition of M by U1 , step 4 b of the description of the universal machine in Theorem If y is 1, then the U1 enters the accepting state and halts. Otherwise, the simulation of the computation of M continues. At first glance, this problem might seem to require the computation of the machine M to be tested on every possible input string—but this is not case. The first 10 transitions of a computation can read at most the first 10 symbols in the input string.
Thus all that is necessary is to check the computation of M on all strings of length 10 or less. If a computation on this finite set of strings requires more than 10 transitions, the answer is yes. If no computation with any string from this set requires more than 10 transitions, the answer is no. A modification of the universal machine can be used to perform this check. Tape 4 will hold the input and tape 5 will serve as a counter. The input to this machine is the representation of M.
The computation consists of the following cycle: 1. The null string is written on tape 4. The string 1 n is written on tape 5. The string on tape 4 is copied to tape 3 and the encoding of state qo is written on tape 2. The computation of M with the input string from tape 4 is simulated on tapes 2 and 3. With each simulated transition, a 1 is erased from tape 5.
If the simulation of M specifies a transition and tape 5 is scanning a blank, the compu- tation halts and accepts. If the simulation of M halts and a 1 is read on tape 5 then - tapes 2, 3 and 5 are erased, - the string 1 n is written on tape 5, and - the next string is generated on tape 4. If the string on tape 4 has length greater than 10, the computation halts and rejects the input. Otherwise, the computation continues with step 3. Let M be a Turing machine that accepts a nonrecursive language L.
Without loss of generality, we may assume that the computation of M continues indefinitely whenever the input is not in L.
Assume that there is a machine H that solves the Halting Problem for M. The halting machine H accepts a string w if M halts with input w. In addition, the computation of H halts in a nonaccepting state for all strings in L. Since H halts for all input strings, it follows that L is recursive. This is a contradiction since our original assumption was that L is nonrecursive.
Thus we conclude that there is no halting machine H. We will show that the Halting Problem is reducible to the question of whether a Turing machine enters a designated state. The machine M0 is constructed from M by adding an additional state qf. The idea behind the reduction that M0 enters qf whenever M halts. The computations of M0 are identical to those of M until M halts. When this occurs, M0 enters qf. Thus M halting is equivalent to M0 entering qf.
Assume that there is a machine S that solves the state problem. The input to S is a rep- resentation of a Turing machine M, input string w, and state qi.
S accepts the input if the computation of M with input w enters state qi. Adding a preprocessor N to S, we construct a machine H that solves the halting problem. By adding the encoding of transitions described above to R M , N constructs the representation of the machine M0. N then adds qf to the end of the string producing R M0 wqf. A computation of H 1. H accepts input R M w if, and only if, M0 enters state qf when run with input w.
That is, whenever M halts with input w. Step 1 is a reduction of the Halting Problem to the State Problem.
0コメント