# MA/CSSE 474 Theory of Computation Enumerability Reduction More

MA/CSSE 474 Theory of Computation Enumerability Reduction More on Dovetailing Dovetailing: Run multiple (possibly an infinite number) of computations "in parallel". S[i, j] represents step j of computation i. S[1, 1] S[2, 1] S[1, 2] S[3, 1] S[2, 2] S[1, 3] S[4, 1] S[3, 2] S[2, 3] S[1, 4 ]

... For every i and j, step S[i, j] will eventually happen. Enumeration Enumerate means "list, in such a way that for any element, it appears in the list within a finite amount of time." We say that Turing machine M enumerates the language L iff, for some fixed state p of M: L = {w : (s, ) |-M* (p, w)}. "p" stands for "print"

A language is Turing-enumerable iff there is a Turing machine that enumerates it. Another term that is often used is recursively enumerable. A Printing Subroutine Let P be a Turing machine that enters state p and then halts: Examples of Enumeration What languages do M1 and M2 enumerate?

SD and Turing Enumerable Theorem: A language is SD iff it is Turing-enumerable. Proof that Turing-enumerable implies SD: Let M be the Turing machine that enumerates L. We convert M to a machine M' that semidecides L: 1. Save input w on another tape. 2. Begin enumerating L. Each time an element of L is enumerated, compare it to w. If they match, accept. The Other Way Proof that SD implies Turing-enumerable:

If L * is in SD, then there is a Turing machine M that semidecides L. A procedure E to enumerate all elements of L: 1. Enumerate all w * lexicographically. e.g., , a, b, aa, ab, ba, bb, 2. As each is enumerated, use M to check it. w3, w2, w1 L? E M M'

Problem with this? yes w The Other Way Proof that SD implies Turing-enumerable: If L * is in SD, then there is a Turing machine M that semidecides L. A procedure to enumerate all elements of L:

1. Enumerate all w * lexicographically. 2. As each string wi is enumerated: 1. Start up a copy of M with wi as its input. 2. Execute one step of each Mi initiated so far, excluding those that have previously halted. 3. Whenever an Mi accepts, output wi. Lexicographic Enumeration M lexicographically enumerates L iff M enumerates the elements of L in lexicographic order. A language L is lexicographically Turing-enumerable iff there is a Turing machine that lexicographically

enumerates it. Example: AnBnCn = {anbncn : n 0}} Lexicographic enumeration: Lexicographically Enumerable = D Theorem: A language is in D iff it is lexicographically Turingenumerable. Proof that D implies lexicographically TE: Let M be a Turing machine that decides L. M' lexicographically generates the strings in * and tests each using M. It outputs those that are accepted by M. Thus M' lexicographically enumerates L. Proof, Continued

Proof that lexicographically Turing Enumerable implies D: Let M be a Turing machine that lexicographically enumerates L. Then, on input w, M' starts up M and waits until: M generates w (so M' accepts), M generates a string that comes after w (so M' rejects), or M halts (so M' rejects). Thus M' decides L. Language Summary IN SD OUT

Semideciding TM H Reduction Enumerable Unrestricted grammar D Deciding TM AnBnCn Diagonalize Lexic. enum Reduction L and L in SD

CF grammar PDA Closure Context-Free AnBn Pumping Closure Regular Regular Expression FSM

a*b* Closure Pumping OVERVIEW OF REDUCTION Reducing Decision Problem P1 to another Decision Problem P2 We say that P1 is reducible to P2 (written P1 P2) if there is a Turing-computable function f that finds,

for an arbitrary instance I of P1, an instance f(I) of P2, and f is defined such that for every instance I of P1, I is a yes-instance of P1 if and only if f(I) is a yes-instance of P2. So P1 P2 means "if we have a TM that decides P2, then there is a TM that decides P1. Example of Turing Reducibility Let P1(n) = "Is the decimal integer n divisible by 4?" P2(n) = "Is the decimal integer n divisible by 2?"

f(n) = n/2 (integer division, which is clearly Turing computable) Then P1(n) is "yes" iff P2(n) is "yes" and P2(f(n)) is "yes" . Thus P1 is reducible to P2, and we write P1 P2. P2 is clearly decidable (is the last digit an element of {0}, 2, 4, 6, 8} ?), so P1 is decidable Reducing Language L1 to L2 Language L1 (over alphabet 1) is mapping reducible to language L2 (over alphabet 2) and we write L1 L2 if

there is a Turing-computable function f : 1* 2* such that x 1*, x L1 if and only if f(x) L2 Using reducibility If P1 is reducible to P2, then If P2 is decidable, so is P1. If P1 is not decidable, neither is P2. The second part is the one that we will use most. Example of Reduction

Compute a function (where x and y are unary representations of integers) multiply(x, y) = 1. answer := . 2. For i := 1 to |y| do: answer = concat (answer, x) . 3. Return answer. So we reduce multiplication to addition. (concatenation)

Using Reduction for Undecidability A reduction R from language L1 to language L2 is one or more Turing machines such that: If there exists a Turing machine Oracle that decides (or semidecides) L2, then the TMs in R can be composed with Oracle to build a deciding (or semideciding) TM for L1. P P means that P is reducible to P. Using Reduction for Undecidability (R is a reduction from L1 to L2) (L2 is in D) (L1 is in D) If (L1 is in D) is false, then at least one of the two

antecedents of that implication must be false. So: If (R is a reduction from L1 to L2) is true and (L1 is in D) is false, then (L2 is in D) must be false. Application: If L1 is a language that is known to not be in D, and we can find a reduction from L1 to L2, then L2 is also not in D. Using Reduction for Undecidability Showing that L2 is not in D:

L1 (known not to be in D) L1 in D But L1 not in D R L2 (a new language whose if L2 in D

decidability we are trying to determine) L2 not in D To Use Reduction for Undecidability 1. Choose a language L1: that is already known not to be in D, and show that L1 can be reduced to L2. 2. Define the reduction R. 3. Describe the composition C of R with Oracle. 4. Show that C does correctly decide L1 iff Oracle exists. We

do this by showing: R can be implemented by Turing machines, Follow this outline in C is correct: If x L1, then C(x) accepts, and proofs that you submit.. We will see If x L1, then C(x) rejects. Example: H = { : TM M halts on } many examples in the next few sessions.

Mapping Reductions L1 is mapping reducible to L2 (L1 M L2) iff there exists some computable function f such that: x* (x L1 f(x) L2). To decide whether x is in L1, we transform it, using f, into a new object and ask whether that object is in L2. Example: DecideNIM(x) = XOR-solve(transform(x)) show H in SD but not in D 1. H is in SD. T semidecides it:

T() = 1. Run M on . 2. Accept. T accepts iff M halts on , so T semidecides H. * Recall: "M halts on w" is a short way of saying "M, when started with input w, eventually halts" H = { : TM M halts on } 2. Theorem: H = { : TM M halts on } is not in D. Proof: by reduction from H:

H H is intuitive, the other direction is not so obvious. H = { : TM M halts on input string w} R (?Oracle) H { : TM M halts on } R is a mapping reduction from H to H: R() = 1. Construct , where M#(x) operates as follows:

1.1. Erase the tape. 1.2. Write w on the tape and move the head to the left end. 1.3. Run M on w. 2. Return . Proof, Continued R() = 1. Construct , where M#(x) operates as follows: 1.1. Erase the tape. 1.2. Write w on the tape and move the head to the left end.

1.3. Run M on w. 2. Return . If Oracle exists, C = Oracle(R()) decides H: C is correct: M# ignores its own input. It halts on everything or nothing. So: H: M halts on w, so M# halts on everything. In particular, it halts on . Oracle accepts. H: M does not halt on w, so M# halts on nothing and thus not on . Oracle rejects.

## Recently Viewed Presentations

• Reply, according to Dr. Felix T. Smith of Stanford Research Institute, to a physicist friend who had said "I'm afraid I don't understand the method of characteristics," as quoted in The Dancing Wu Li Masters: An Overview of the New...
• Assessment of Student Progress in Reading and Writing ... repetitions, omissions, mispronunciation Categorize according to cueing systems: semantic (meaning is similar) graphophonic (looks similar) syntactic (grammatically acceptable) Informal Reading Inventory (IRI) Commercial tests to assess ...
• Pertemuan 18 LONG-TERM LIABILITIES
• Understand Sun Solaris 10 file system ZFS. Understand the Mac OS X file system. Understand the various Windows file systems, including FAT and NTFS. Understand CD-ROM and DVD file systems. Understand the EFS recovery key agent
• BUILD OR ENHANCE YOUR RECURING REVENUE STREAM. OWS is designed with a dedicated reseller portal to allow you to control customer access to features and functionality based on your RMR business model. OWS even includes features to enable time based...
• location and timing of next the TTC meeting . to be organized around February 2020. CERN offered to host us, very likely in the week starting February 3rd; after the Chinese New Year…. After some discussion we agreed that the...
• History of fusion research in Czech Rep. IPP Prague founded in 1959 Interaction of RF waves with magnetized plasmas Interaction of electron beams with magnetized plasmas Linear experiments ELMAN a VF-1 Godfather of tokamaks (and H-bomb) visited IPP Prague in...
• Introduction to Literary Theory, Feminist and Gender Criticism "The Story of an Hour" and "The English Canon" What do we mean when we say "Feminist Criticism"?