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