Understanding Turing Machines and Busy Beaver Problem in Computer Science Theory

Delve into the realm of Turing machines, the Busy Beaver problem, palindromes, and incrementing algorithms. Explore the configurations of a Turing machine tape, the maximum number of 1s a machine can print and still halt, algorithms to determine palindromes, and tape setup for incrementing.

• Turing Machines
• Busy Beaver Problem
• Palindromes
• Incrementing Algorithms
• Computer Science

lynx_412 Follow

Uploaded on Sep 21, 2024 | 0 Views

Download Presentation

Please find below an Image/Link to download the presentation.

The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.

Presentation Transcript

1. Turing Machines Turing Machines Part Two Part Two - -Common TMs Common TMs CSCI 432 Computer Science Theory CSCI 432 Computer Science Theory

2. Exercise Exercise Given this TM and this tape of 0s, determine the configuration of the tape after the TM halts. 1/1,L 0/1,R A B halt 1/1,R 0/1,L | > | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |

3. Busy Beaver Problem Busy Beaver Problem The previous TM is an example of a 2-State "Busy Beaver" Turing Machine. Given an n-state TM with = {0,1}, what is the max number of 1s the machine can print on a tape of 0s and still halt? S(1) S(2) S(3) S(4) S(5) S(6) proven max is 1 proven max is 4 proven max is 6 proven max is 13 theoretical max is 4098 may never be known, but is approximately 4.6 x 101439 photo: jeremykun.com

4. Even Palindromes Even Palindromes What is the algorithm to determine if a string is a palindrome? | > | a | b | b | b | b | a | - | - | - | a/a,R b/b,R -/-,L a/-,L a/-,R b/b,L -/-,R a/a,L A B C D -/-R a/a,L b/-,R -/-,L b/-,L b/b,L -/-,L a/a,R b/b,R accept G E F Where are the transitions to the reject halting state?

5. Increment Incrementalgorithm algorithm 10 + 1 = 11 11 + 1 = 100 1011 + 1 = 1100 1100 + 1 = 1101 Non-TM Algorithm: go to far right (least significant digit) repeat if 0 or blank, write 1 and halt if 1, write 0 and go left

6. Increment Incrementtape setup tape setup Given 1) 11 + 1 = 100 (we had to add a column on the far left) 2) the tape starts on the left with infinite space to the right We have two choices of how to store binary numbers on the tape: A) store numbers in a fixed width (eg 8 bits) The number 4 is stored as 00000100 obviously, leads to overflow issues B) reverse the order of significance The number 4 is stored as 001 (instead of 100)

7. Increment IncrementTuring Machine Turing Machine Assuming reverse order of precedence, so that 1+1 = >1 >01 4+1 = >001 >101 7+1 = >111 >0001 1+1 = 10 100+1=101 111+1=1000 Turing Machine: 1/1,L 1/0,R >/>,R 0/1,L /1,L A B halt 0/0,L

8. Decrement Decrement Again, assuming reverse order of precedence, so that 4-1 = >001 >110 3-1 = >110 >010 1-1 = >1 >0 100-1=011 011-1=010 1-1=0 Turing Machine: 1/1,L 0/1,R >/>,R 1/0,L A B halt 0/0,L

9. Decrement Decrement version 2 version 2 Suppose we want the number to slowly disappear. 4-1 = >001 >11 3-1 = >11 >01 2-1 = >01 >1 1-1 = >1 > 100-1=11 11-1=10 10-1=1 1-1= Turing Machine: D 1/1,L 0/1,R / ,L >/>,R 1/0,R 0/ ,L 1/1,L 1/1,L 0/0,L 0/0,L A B C halt

10. Addition Addition Given our previous TMs that increment and decrement, and the tape configuration >A#B# How would we create a TM to add A and B? For example, A=2 and B=3 | > | A | 0 | 1 | B | 1 | 1 | - | - | - |