DOC PREVIEW
UVA CS 302 - Undecidability in Theory and Practice

This preview shows page 1-2-3-26-27-28 out of 28 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 28 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 28 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 28 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 28 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 28 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 28 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 28 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

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 = 1Start010...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
Download Undecidability in Theory and Practice
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Undecidability in Theory and Practice and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Undecidability in Theory and Practice 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?