Slide 1MenuPS5, Problem 5Impossibility of CopyingNevertheless, HALTUTM is UndecidableComputability in Theory and Practice (Intellectual Computability Discussion on TV Video)Ali G ProblemSlide 8Slide 9Ali G was Right!Busy BeaversThe “Busy Beaver” GameBusy Beaver: N = 1Slide 14Slide 15Slide 16Slide 17Slide 18Slide 19Slide 20What is BB(6, 2)?Slide 22Slide 23Busy Beaver NumbersIs there a language problem?Is LBB Decidable?LBB is UndecidableChallengesClass 19: Undecidability in Theory and PracticeClass 19: Undecidability in Theory and PracticeDavid EvansDavid Evanshttp://www.cs.virginia.edu/evanshttp://www.cs.virginia.edu/evanscs302: Theory of Computationcs302: Theory of ComputationUniversity of Virginia Computer ScienceUniversity of Virginia Computer Science2Lecture 19: Undecidability in Theory and PracticeMenu•PS5, Problem 5•Erudite Discussion on Undecidability•Busy Beaver Problem3Lecture 19: Undecidability in Theory and PracticePS5, Problem 5Consider a one-tape Turing Machine that is identical to a regular Turing machine except the input may not be overwritten. That is, the symbol in any square that is non-blank in the initial configuration must never change. Otherwise, the machine may read and write to the rest of the tape with no constraints (beyond those that apply to a regular Turing Machine).a. What is the set of languages that can be recognized by an unmodifiable-input TM? b. Is HALTUTM decidable?4Lecture 19: Undecidability in Theory and PracticeImpossibility of Copyinginput (unmodifiable)0 1 0 0 1 1 1 0 0 0How can the TM keep track of which input square to copy next?Option 1: Use the writable part of the tape.Problem: can’t read it without losing head positionOption 2: Use the FSM states.Problem: there is a finite number of them!Hence, it is equivalent to a DFA regular languages5Lecture 19: Undecidability in Theory and PracticeNevertheless, HALTUTM is UndecidableProve by reducing HALTTM to HALTUTM:HALTTM(<M, w>) = HALTUTM(<MUw, ε>) where MUw = an unmodifiable-TM that ignores the input, writes a # on the tape, followed by w, then, simulates M on the tape starting at the first square after the #, treating the # as if it is the left edge of the tape.6Lecture 19: Undecidability in Theory and PracticeComputability in Theory and Practice(Intellectual Computability Discussion on TV Video)7Lecture 19: Undecidability in Theory and PracticeAli G Problem•Input: a list of numbers (mostly 9s)•Output: the product of the numbersIs LALIG decidable?LALIG = { < k0, k1, …, kn, p> | each ki represents a number and p represents a number that is the product of all the kis. numbersYes. It is easy to see a simple algorithm (e.g., elementary school multiplication) that solves it.Can real computers solve it?10Lecture 19: Undecidability in Theory and PracticeAli G was Right!•Theory assumes ideal computers:–Unlimited, perfect memory–Unlimited (finite) time•Real computers have:–Limited memory, time, power outages, flaky programming languages, etc.–There are many decidable problems we cannot solve with real computer: the actual inputs do matter (in practice, but not in theory!)11Lecture 19: Undecidability in Theory and PracticeBusy Beavers12Lecture 19: Undecidability in Theory and PracticeThe “Busy Beaver” Game•Design a Turing Machine that:–Uses k symbols (e.g., “0” and “1”)–Starts with a tape of all “0”s–Eventually halts (can’t run forever)–Has n states (not counting qAccept and qReject)•Goal is to run for as many steps as possible (before halting)•2-way infinite tape TMTibor Radó, 196213Lecture 19: Undecidability in Theory and PracticeBusy Beaver: N = 1Start010...0 0 0 0 0 0 0 0 0BB(1, 2) = 1 Most steps a 1-state machine that halts can make qAccept0 0 0 0 0 0 0 014Lecture 19: Undecidability in Theory and PracticeAStartBInput: 0Write: 1Move: 0...0 0 0 0 0 0 0 0 0Input: 0Write: 1Move: HInput: 1Write: 1Move: /Input: 1Write: 1Move: BB(2, 2) = ?0 0 0 0 0 0...15Lecture 19: Undecidability in Theory and PracticeAStartBInput: 0Write: 1Move: Input: 0Write: 1Move: HInput: 1Write: 1Move: /Input: 1Write: 1Move: Step 21...0 0 0 0 0 0 0 0 00 0 0 0 0 0...16Lecture 19: Undecidability in Theory and PracticeAStartBInput: 0Write: 1Move: Input: 0Write: 1Move: HInput: 1Write: 1Move: /Input: 1Write: 1Move: Step 31...1 0 0 0 0 0 0 0 00 0 0 0 0 0...17Lecture 19: Undecidability in Theory and PracticeAStartBInput: 0Write: 1Move: Input: 0Write: 1Move: HInput: 1Write: 1Move: /Input: 1Write: 1Move: Step 41...1 0 0 0 0 0 0 0 00 0 0 0 0 0...18Lecture 19: Undecidability in Theory and PracticeAStartBInput: 0Write: 1Move: Input: 0Write: 1Move: HInput: 1Write: 1Move: /Input: 1Write: 1Move: Step 51...1 0 0 0 0 0 0 0 00 0 0 0 0 1...19Lecture 19: Undecidability in Theory and PracticeAStartBInput: 0Write: 1Move: Input: 0Write: 1Move: HInput: 1Write: 1Move: /Input: 1Write: 1Move: Step 61...1 0 0 0 0 0 0 0 00 0 0 0 1 1...20Lecture 19: Undecidability in Theory and PracticeAStartBInput: 0Write: 1Move: Input: 0Write: 1Move: HInput: 1Write: 1Move: /Input: 1Write: 1Move: Halted1...1 0 0 0 0 0 0 0 00 0 0 0 1 1...BB(2, 2) 6(Actually, known that BB(2,2) = 6)21Lecture 19: Undecidability in Theory and PracticeWhat is BB(6, 2)?22Lecture 19: Undecidability in Theory and PracticeAStartBCDEF0/1/R1/0/L0/0/R1/0/R0/1/L1/1/R0/0/L1/0/L0/0/R1/1/R0/1/LH1/1/H6-state machine found by Buntrock and Marxen, 200123Lecture 19: Undecidability in Theory and
View Full Document