CSE 105 Theory of Computation

CSE 105 Theory of Computation

CSE 105 THEORY OF COMPUTATION Spring 2019 https://cseweb.ucsd.edu/classes/sp19/cse105-a/ Today's learning goals Sipser Ch 3.1, 3.2 Design TMs using different levels of descriptions. Give high-level description for TMs (recognizers and enumerators) used in constructions

Prove properties of the classes of recognizable and decidable sets. Describe several variants of Turing machines and informally explain why they are equally expressive. State and use the Church-Turing thesis. An example L = { w#w | w is in {0,1}* } Idea for Turing machine Zig-zag across tape to corresponding positions on either side of '#' to check whether these positions agree. If they do not, or if there is no '#', reject. If they do, cross them off. Once all symbols to the left of the '#' are crossed off, check for

any symbols to the right of '#': if there are any, reject; if there aren't, accept. How would you use this machine to prove that L is decidable? Q={q1,q2,q3,q4,q5,q6,q7, q8,qaccept,qreject} = {0,1,#} = {0,1,#,x,_ } All missing transitions have output (qreject, _, R) Fig 3.10 in Sipser

Computation on input 0#0? Configuration u q v for current tape uv (and then all blanks), current head location is first symbol of v, current state q Computation on input 0# ? Describing TMs Sipser p. 159

Formal definition: set of states, input alphabet, tape alphabet, transition function, state state, accept state, reject state. Implementation-level definition: English prose to describe Turing machine head movements relative to contents of tape. High-level desciption: Description of algorithm, without implementation details of machine. As part of this description, can "call" and run another TM as a subroutine. An example Which of the following is an implementation-level description

of a TM which decides the empty set? M = "On input w: A. reject." B. sweep right across the tape until find a non-blank symbol. Then, reject." C. If the first tape symbol is blank, accept. Otherwise, reject." D. More than one of the above. E. I don't know. Turing recognizable languages Turing decidable languages Context-free languages

Regular languages Closure Theorem: The class of decidable languages over fixed alphabet is closed under union. Proof: Let WTS Closure Theorem: The class of decidable languages over fixed alphabet is closed under union. Proof: Let L1 and L2 be languages over and suppose M1 and M2 are TMs deciding these languages. We will define

a new TM, M, via a high-level description. We will then show that L(M) = L1 U L2 and that M always halts. Closure Theorem: The class of decidable languages over fixed alphabet is closed under union. Proof: Let L1 and L2 be languages and suppose M1 and M2 are TMs deciding these languages. Construct the TM M as "On input w, 1. Run M1 on input w. If M1 accepts w, accept. Otherwise, go to 2. 2. Run M2 on input w. If M2 accepts w, accept. Otherwise, reject." Correctness of construction: Where do we use decidability?

WTS L(M) = L1 U L2 and M is a decider. Closure Good exercises can't use without proof! (Sipser 3.15, 3.16) The class of decidable languages is closed under Union Concatenation Intersection Kleene star Complementation

The class of recognizable languages is closed under Union Concatenation Intersection Kleene star Variants of TMs Section 3.2 Scratch work, copy input,

Multiple tapes Parallel computation Nondeterminism Printing vs. accepting Enumerators More flexible transition function Can "stay put" Can "get stuck" lots of examples in exercises to Chapter 3 Payoff: in high-level description of TM, can simulate converstion to other variant.

"Equally expressive" Model 1 Model 2 Model 1 is equally expressive as Model 2 iff every language recognized by some machine in Model 1 is recognizable by some machine in Model 2, and every language recognized by some machine in Model 2 is recognizable by some machine in Model 1. Nondeterministic TMs

Sipser p. 178 Transition function Q x P(Q x x {L,R}) Sketch of proof of equivalence: A. Given TM, build nondeterminstic TM recognizing same language. B. Given nondeterministic TM, build (deterministic) TM recognizing same language. Idea: Try all possible branches of nondeterministic computation. 3 tapes: "read-only" input tape, simulation tape, tape tracking nondeterministic braching.

Multitape TMs Sipser p. 176 As part of construction of machine, declare some finite number of tapes that are available. Input given on tape 1, rest of the tapes start blank. Each tape has its own read/write head. Transition function Q x k Q x k x {L,R}k Sketch of proof of equivalence: Given TM, build multitape TM recognizing same language. Given k-tape TM, build (1-tape) TM recognizing same

language. Idea: Use delimiter to keep tape contents separate, use special symbol to indicate location of each read/write head Very different model: Enumerators Sipser p. 180 Produce language as output rather than recognize input Computation proceeds according to transition function. Finite State Control

a b a b Unlimited work tape Printer .

At any point, machine may "send" a string to printer. L(E) = { w | E eventually, in finite time, prints w} Enumerators What about machines accept input? Finite State Control

a b Can L(E) be infinite? A. No, strings must be printed in finite time. thatB.produce than No, stringsoutput must be rather all be finite length.

C. Yes, it may happen if E does not halt. D. Yes, all L(E)Computation are infinite. proceeds according to transition E. I don't know. function. a b Unlimited tape .

At any point, machine may "send" a string to printer. L(E) = { w | E eventually, in finite time, prints w} Set of all strings "For each , there is an enumerator whose language is the set of all strings over ." A. True B. False C. Depends on . D. I don't know.

Set of all strings "For each , there is an enumerator whose language is the set of all strings over ." A. True B. False C. Depends on . D. I don't know. Standard string ordering: order strings first by length, then dictionary order.

(p. 14) Recognition and enumeration Sipser Theorem 3.21 Theorem: A language L is Turing-recognizable iff some enumerator enumerates L. Proof: Assume L is Turing-recognizable. WTS some enumerator enumerates it. Assume L is enumerated by some enumerator. WTS L is Turing-recognizable.

Recognition and enumeration Sipser Theorem 3.21 Assume the enumerator E enumerates L. WTS L is Turingrecognizable. We'll use E in a subroutine for high-level description of Turing machine M that will recognize L. Define M as follows: M = "On input w, 1. Run E. Every time E prints a string, compare it to w. 2. If w ever appears as the output of E, accept. Correctness?

Recognition and enumeration Sipser Theorem 3.21 Assume L is Turing-recognizable. WTS some enumerator enumerates it. Let M be a TM that recognizes L. We'll use M in a subroutine for highlevel description of enumerator E. Let s1, s2, be a list of all possible strings of *. Define E as follows: E = "Repeat the following for each value of i=1,2,3 1. Run M for i steps on each input s 1, , si 2. If any of the i computations of M accepts, print out the accepted string. Correctness?

Variants of TMs Scratch work, copy input, Multiple tapes Parallel computation Nondeterminism Printing vs. accepting Enumerators All these models are More flexible transition equallyfunction

expressive! Can "stay put" Can "get stuck" lots of examples in exercises to Chapter 3 Also: wildly different models -calculus, Post canonical systems, URMs, etc. Church-Turing thesis Sipser p. 183

Wikipedia "self-contained step-by-step set of operations to be performed" CSE 20 textbook "An algorithm is a finite sequence of precise instructions for performing a computation or for solving a problem." Church-Turing thesis Each algorithm can be implemented by some Turing machine.

Recently Viewed Presentations

  • Por vs. Para

    Por vs. Para

    Por- duration of time Por vs. Para POR Duration of time Voy a estudiar por dos horas. "Along" or "Through" Quiero viajar por Madrid. Voy a caminar por el parque. General location Hay un banco por aquĆ­. (There is a...
  • Reflections on Leadership: Looking Back to Move Forward

    Reflections on Leadership: Looking Back to Move Forward

    Reflections on Leadership: Looking Back to Move Forward. ... take responsibility for the design of work and workspace to prevent and mitigate error, and serve as ... RWJF's Executive Nurse Program, RWJF's Health Policy Program, Hartford Foundation's Building Academic Geriatric...
  • NWSS Library's Chicago Bootcamp Why do we cite

    NWSS Library's Chicago Bootcamp Why do we cite

    NWSS Library's Chicago Bootcamp. Citations give credit to the sources of information you used in your research. Citations show that your product is your own work. In other words, you have not copied information from other sources. The University of...
  • Animation With Momentum - twvideo01.ubm-us.net

    Animation With Momentum - twvideo01.ubm-us.net

    Synthesis of Constrained Walking SkillsStelianCoros, Philippe Beaudoin, Kang Kang Yin, Michiel van de Panne Siggraph Asia 08. Take-Away: PCA Hypothesis. Principle Component Analysis (PCA) is a technique used for the lossy compression of vector data sets. A 3 DOF analogy...
  • Impact of Genomics on Genetic Improvement Paul VanRaden

    Impact of Genomics on Genetic Improvement Paul VanRaden

    Proven bulls: 2013 vs. 2010 NM$ Net Merit, April 2010 827 654 622 615 609 602 595 592 592 588 585 583 579 577 576 569 568 563 559 559 557 556 556 550 549 548 547 547 545 538...
  • CSN09101 Networked Services

    CSN09101 Networked Services

    CSN09101 Networked Services Week 6 : Firewalls + Security Module Leader: Dr Gordon Russell Lecturers: G. Russell, J. Jackson
  • Poetic Form and Meaning - WordPress.com

    Poetic Form and Meaning - WordPress.com

    Simple diction. Narrative (tell a story) rather than lyric (focus on emotions) Objective (3rd-person narrators) rather than subjective. May contain dialogue and archetypal figures. One of the oldest poetic forms in the English language
  • Transducers PHYS3360/AEP3630 Lecture 33 1 Terminology  Transducers convert

    Transducers PHYS3360/AEP3630 Lecture 33 1 Terminology Transducers convert

    Linear Variable Differential Transformer. Positional Sensors: Inductive Proximity Switch. Detects the presence of metallic objects (non-contact) via changing inductance ... Stepper motors. AC. Stepper motor. Brushed motor - permanent magnets on armature, rotor acts as electromagnet.