Busy Beaver

June 24, 2014

Yesterday was Alan Turing’s birthday, so today we will write a program for a turing machine.

The Busy Beaver is a turing machine that performs the maximum work for a given configuration of machine; the concept was invented by Tibor Radó in his 1962 paper On Non-Computable Functions. We won’t look at the underlying theory, although it is fascinating if you have the time. Instead, we’ll be content to implement the first few busy beavers. Here are the two-symbol busy beavers for one, two, three and four states, from Wikipedia; the two symbols are 0 and 1, the states are letters A through D plus the halting state H, and the moves L and R are left and right:

  A
0 1RH
1 unused
  A B
0 1RB 1LA
1 1LB 1RH
  A B C
0 1RB 0RC 1LC
1 1RH 1RB 1LA
  A B C D
0 1RB 1LA 1RH 1RD
1 1LB 0RC 1LD 0RA

Your task is to implement the four busy beavers. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Advertisement

Pages: 1 2

Posted by programmingpraxis
Filed in Exercises
3 Comments »

3 Responses to “Busy Beaver”

  1. Paul said
    June 24, 2014 at 2:49 PM

    In Python: Codepad. For my hero: Alan Turing.

  2. matthew said
    June 25, 2014 at 11:23 AM

    (I think machine 4 should have 0LC for the 1-B entry there).

    It’s easy to translate Turing Machine programs into Markov programs, so here’s the 3-state machine:

    A0 => 1B
A1 =>. 1H

B0 => 0C
B1 => 1B

0C0 => C01
1C0 => C11
0C1 => A01
1C1 => A11

A$ => A0$
$A => $0A
B$ => B0$
$B => $0B
C$ => C0$
$C => $0C

    and a run:

    ./markov.pl < bb3.txt '$A$'
$A$
$A0$
$1B$
$1B0$
$10C$
$10C0$
$1C01$
$C111$
$0C111$
$A0111$
$1B111$
$11B11$
$111B1$
$1111B$
$1111B0$
$11110C$
$11110C0$
$1111C01$
$111C111$
$11A1111$
$111H111$

    And the 4-state machine:

    A0 => 1B
0A1 => B01
1A1 => B11

0B0 => A01
1B0 => A11
0B1 => C00
1B1 => C10

C0 =>. 1H
0C1 => D01
1C1 => D11

D0 => 1D
D1 => 0A

A$ => A0$
$A => $0A
B$ => B0$
$B => $0B
C$ => C0$
$C => $0C
D$ => D0$
$D => $0D

    [http://matthewarcus.wordpress.com/2014/01/08/markov-computation/]

Leave a Reply

Fill in your details below or click an icon to log in:

Gravatar
WordPress.com Logo

You are commenting using your WordPress.com account. ( Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. ( Log Out /  Change )

Cancel

Connecting to %s

%d bloggers like this: