Important Undecidable Problems

Important Undecidable Problems

Class 19: Undecidability in Theory and Practice cs302: Theory of Computation University of Virginia Computer Science David Evans http://www.cs.virginia.edu/evans Menu PS5, Problem 5 Erudite Discussion on Undecidability Busy Beaver Problem Lecture 19: Undecidability in Theory and Practice 2 PS5, Problem 5 Consider 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? Lecture 19: Undecidability in Theory and Practice

3 Impossibility of Copying 0 1 0 0 1 1 1 0 0 0 input (unmodifiable) How can the TM keep track of which input square to copy next? Option 1: Use the writable part of the tape. Problem: cant read it without losing head position Option 2: Use the FSM states. Problem: there is a finite number of them! Hence, it is equivalent to a DFA regular languages Lecture 19: Undecidability in Theory and Practice 4 Nevertheless, HALTUTM is Undecidable Prove by reducing HALTTM to HALTUTM: HALTTM() = HALTUTM() 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. Lecture 19: Undecidability in Theory and Practice 5 Computability in Theory and Practice

(Intellectual Computability Discussion on TV Video) Lecture 19: Undecidability in Theory and Practice 6 Ali G Problem Input: a list of numbers (mostly 9s) Output: the product of the numbers LALIG = { < k0, k1, , kn, p> | each ki represents a number and p represents a number that is the product of all the kis. numbers Is LALIG decidable? Yes. It is easy to see a simple algorithm (e.g., elementary school multiplication) that solves it. Can real computers solve it? Lecture 19: Undecidability in Theory and Practice 7 Ali 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!) Lecture 19: Undecidability in Theory and Practice 10 Busy Beavers Lecture 19: Undecidability in Theory and Practice 11 The Busy Beaver Game Design a Turing Machine that: Uses k symbols (e.g., 0 and 1) Starts with a tape of all 0s Eventually halts (cant 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 TM Tibor Rad, 1962 Lecture 19: Undecidability in Theory and Practice 12 Busy Beaver: N = 1 0 0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 ... 01 Start qAccept BB(1, 2) = 1 Most steps a 1-state machine that halts can make Lecture 19: Undecidability in Theory and Practice 13

... 0 0 0 0 0 0 0 0 0 0 0 0 0 Input: 0 Write: 1

Move: Start A Input: 0 Write: 1 Move: B Input: 1 Write: 1 Move: / H Input: 1 Write: 1 Move: BB(2, 2) = ? Lecture 19: Undecidability in Theory and Practice 14 0 0

0 ... ... 0 0 0 0 0 0 1 0 0 0 0 0

0 0 0 0 ... Input: 0 Write: 1 Move: Start A Input: 0 Write: 1 Move: B Input: 1 Write: 1 Move: / H Input: 1

Write: 1 Move: Step 2 Lecture 19: Undecidability in Theory and Practice 15 ... 0 0 0 0 0 0 1 1 0 0

0 0 0 0 0 0 ... Input: 0 Write: 1 Move: Start A Input: 0 Write: 1 Move: B Input: 1 Write: 1 Move: /

H Input: 1 Write: 1 Move: Step 3 Lecture 19: Undecidability in Theory and Practice 16 ... 0 0 0 0 0 0 1 1

0 0 0 0 0 0 0 0 ... Input: 0 Write: 1 Move: Start A Input: 0 Write: 1 Move: B

Input: 1 Write: 1 Move: / H Input: 1 Write: 1 Move: Step 4 Lecture 19: Undecidability in Theory and Practice 17 ... 0 0 0 0 0 1

1 1 0 0 0 0 0 0 0 0 ... Input: 0 Write: 1 Move: Start A Input: 0

Write: 1 Move: B Input: 1 Write: 1 Move: / H Input: 1 Write: 1 Move: Step 5 Lecture 19: Undecidability in Theory and Practice 18 ... 0 0 0 0

1 1 1 1 0 0 0 0 0 0 0 0 ... Input: 0 Write: 1 Move: Start

A Input: 0 Write: 1 Move: B Input: 1 Write: 1 Move: / H Input: 1 Write: 1 Move: Step 6 Lecture 19: Undecidability in Theory and Practice 19 ... 0 0

0 0 1 1 1 1 0 0 0 0 0 0 0 0 ...

Input: 0 Write: 1 Move: Start A Input: 0 Write: 1 Move: B Input: 1 Write: 1 Move: / H Input: 1 Write: 1 Move: BB(2, 2) 6 (Actually, known that BB(2,2) = 6) Lecture 19: Undecidability in Theory and Practice 20 Halted

What is BB(6, 2)? Lecture 19: Undecidability in Theory and Practice 21 0/0/R B 0/1/R Start A C 1/1/R 0/1/L 1/0/L 1/0/R 1/0/L D F E

0/0/L 0/1/L 1/1/H 1/1/R 0/0/R H 6-state machine found by Buntrock and Marxen, 2001 Lecture 19: Undecidability in Theory and Practice 22 0/0/R C B 0/1/R Start A 0/1/L 1/0/L

1/0/L F 1/0/R E D 1/1/R 0/1/L 1/1/H 1/1/R 0/0/L 0/0/R H (1730 digits) Best found before 2001, only 925 digits! 3002327716523562828955103018341340185147754337246752500 3733818017352142407603832658819120829782028766989840178

6071345848280422383492822716051848585583668153797251438 6185617302094154876855700785386587573048574872220400307 6984404509887136708761507913831103435316464107791920989 0837164477363289374225531955126023251172259034570155087 3036836546308741559908225161299384258306913786072736707 0819016052553407704003922659307399792317015477535862985 0421712513378527086223112680677973751790032937578520017 6667922468399088559203629337677447608701284468834554778 0631649160185578442686076902794454279800615269316745282 1336689917460886106486574189015401194034857577718253065 5416326563343142423255924867001185067165813034232717489 6542616040979717307371668882728143590463944560592817525 4048321109306002474658968108793381912381812336227992839 9308330859334788531765747027760628582891565683922959635 8626365413938385676472805139496555440968845657812274329 6319960808368094536421039149584946758006509160985701328 9970263017087602355002395981194105921426216696145528272 4442921741646549436389169711396531689266061170929004858 0677566178715752354594049016719278069832866522332923541 3702930596679960013193766985516838488514746251520945671 1061545198683989449088568708224497877455145320435858866 1593979763935102896523295803940023673203101744986550732 4968504369997537113430673286761581462692927233756620156 1282692410545484965841096157403121144061108897534989915 6714888681952366018086246687712098553077054825367434062 6717567600703889221174349326334447731387837140237358987 1279027828837719826038006510507579292523945345062299920 8297579584893448886278127629044163292251815410053522246 0845527615133839346231290832669493773809504666431216897 46511996847681275076313206

http://drb9.drb.insel.de/~heiner/BB/index.html Lecture 19: Undecidability in Theory and Practice 23 Busy Beaver Numbers BB(1) = 1 BB(2) = 6 BB(3) = 21 BB(4) = 107 BB(5) = Unknown! The best found so far is 47,176,870 BB(6) > 102879 Lecture 19: Undecidability in Theory and Practice 24 Is there a language problem? LBB= { | where n and k represent integers and s is the maximum number of steps a TM

with n non-final states and k tape symbols can run before halting } Lecture 19: Undecidability in Theory and Practice 25 Is LBB Decidable? Lecture 19: Undecidability in Theory and Practice 26 LBB is Undecidable Proof by reduction: Assume MBB exists that decides LBB HALTTM() = n = number of states in M k = number of symbols in Ms tape alphabet find s by trying s = 1, 2, ... until MBB accepts simulate M on w for up to s steps if it halts, accept if it doesnt complete, reject Lecture 19: Undecidability in Theory and Practice 27 Challenges The standard Busy Beaver problem is defined for a doubly-infinite tape TM. For the oneway infinite tape TM, what is BB(4, 2)?

Find a new record BB number http://drb9.drb.insel.de/~heiner/BB/index.html Exam 2: one week from today. Lecture 19: Undecidability in Theory and Practice 28

Recently Viewed Presentations

  • Welcome to Harlaw Academy 2019-20 Origins 1874 (1893

    Welcome to Harlaw Academy 2019-20 Origins 1874 (1893

    Kaimhill. and all other parts of City. ... In school, on time, behaving and producing your best work, first time, on time every time. Taking an active role in your learning; the level you are working at, what to do...
  • Residential Services Curriculum

    Residential Services Curriculum

    Create Wordle for traditions, race, sexual-orientation, gender, holidays, beliefs Cultural Competency describes our knowledge, value, appreciation, and respect for those with whom we interact (individuals served, personnel, families/caregivers and other stakeholders).
  • U-boat Radio Room

    U-boat Radio Room

    HF/MF Antennas. 12.5 mm galvanized steel wire - 14 meters forward, 16 meters aft. Used to transmit and receive HF radio messages and transmit MF bearing signals. Generally forward antenna transmitted, after antennas received. If possible the boat was pointed...
  • Omnicare Diabetes Health Management Program

    Omnicare Diabetes Health Management Program

    Polypharmacy and Avoidng The Use of High Risk Medications Kristin Kim, RPh Omnicare Consultant Pharmacist June 13, 2014 * * * * * * * * * * * * * * * Polypharmacy * Polypharmacy * Polypharmacy * I...
  • Cowtown Lone Star Books - Denton ISD

    Cowtown Lone Star Books - Denton ISD

    Successful Testers Are Academic Readers. Presented by Bonnie McCormick, Anna Modrow and Rhonda Thomas, Denton ISD Middle School Librarians. Creative Contributions by Sherry Brandt, Kim Johnson, Donna Kearley, Kelly Korenek, Anna Modrow, Margarete Neale, Sandy Noles, Carol Richmond, Leslye Rosin,...
  • Gender Specific Effects of Early-Life Events on Adult Lifespan

    Gender Specific Effects of Early-Life Events on Adult Lifespan

    Сравнительный анализ тенденций смертности в странах бывшего Советского Союза
  • Cosmology with the South Pole Telescope Zak Staniszewski (Case)

    Cosmology with the South Pole Telescope Zak Staniszewski (Case)

    You should be excited. We want Dn/Dz. Remember, these are only our slam dunk cluster candidates. Only from 40 square degrees. We currently have 200 square degrees. Second 100 sq degree field is deeper
  • Welcome to Lovinggood Middle School

    Welcome to Lovinggood Middle School

    Reading Bowl. Drama Club. Distinguished Gentlemen. Junior Beta . STARS. FCCLA. Science Fair Club. Yearbook. FBLA. Sources of Strength. News Team. More may be formed upon student interest. 90-100 A. 80-89 B. 74-79 C. 70-73 D. 0-69 F. Students also...