Your challenge in each of these problems is to construct a Turing machine that computes things.

Rules:

  • Use only standard Turing machines except where otherwise noted.
  • Your score is \(\text{states} \times \text{colors}^2\). Like golf, you are trying to minimize your score for each challenge.
    • If you allow your machine to make a null move, it becomes \((\text{states} + 1) \times \text{colors}^2\).
  • Input and output formats are up to you. Usually the input consists of one or more strings of ones separated by single blanks.
  • You are absolutely free to break these rules and try to do these using other restricted programming environments. Lambda calculus, Brainf***, anything you want. You have to come up with your own scoring system, however.
  • Please add your own challenges to this page! They are ordered roughly by perceived difficulty.
  • Leave comments on the talk page. Anything that's not a Turing machine or a challenge goes there.
  • If you believe that your Turing machine is the simpliest one, add a proof.

Contents

Infinity

Infinity is not a number?

King2218's answer

Why not?

0 * 1 r 0

King2218 (talk) 14:58, April 8, 2014 (UTC)

Googology Noob's answer

Sadly, the above does not halt. This ITTM program does however:

0 _ 1 r 0

L 1 1 r halt

Addition

Given two inputs \(n\) and \(m\), compute \(n + m\).

Deedlit's answer

Assuming \(n\) and \(m\) are strings of ones separated by a space, we can use:

0 _ 1 r 1
0 1 1 r 0
1 _ _ l 2
1 1 1 r 1
2 1 _ l halt
2 _ _ l halt

It just fills in the blank and eliminates the rightmost 1. Deedlit11 (talk) 00:17, April 4, 2013 (UTC)

FB100Z's answer

0 1 _ r 1
1 1 * r *
1 _ 1 * halt

This one's even simpler, removing the leftmost 1 then filling the blank. Provably the simplest possible machine that does this job. FB100Ztalkcontribs 03:21, April 4, 2013 (UTC)

Googleaarex's answer

0 1 1 r 0
0 _ 1 r 1
1 1 1 r 1
1 _ _ l 2
2 1 _ * halt

It take A+B+3 steps to halt. AarexTiao 00:02, December 10, 2013 (UTC)

Googleaarex's answer V2

0 1 1 r 0
0 _ 1 l 1
1 1 1 l 1
1 _ _ r 2
2 1 _ * halt

It take (A+1)*2+1 steps to halt. ~~~~

Proof for the simplest machine

FB100Z's Turing machine is actually the simpliest one that performs addition. To prove it, consider the starting rule: if we have only 1 state, then there are 4 possible non-trivial cases:

0 1 _ r 0
0 1 1 r 0
0 1 _ l 0
0 1 1 l 0

First case is unreasonable: we remove the first string entirely, and can't return it.

Second case is much closer to the goal, we can apply the ruleset:

0 1 1 r 0
0 _ 1 r halt

However, it leads to n+m+1, and thus we don't match the condition with it.

Rest of rules is also can't lead to n+m, since we don't have the rule that forces the head to go to the right and fill the blank.

FB100Z's answer (BF)

,>,[-<+>]<.

Comparison

Given two inputs \(n\) and \(m\), determine whether \(n < m\), \(n = m\), or \(n > m\).

Aarex's answer

0 1 * l 0
0 _ * r 1
1 1 _ r 2
1 _ < * halt
2 1 * r 2
2 _ * r 3
3 1 * r 3
3 _ * l 4
4 1 _ l 5
4 _ > * halt
5 1 * l 5
5 _ * l 0

Aarex (talk) 00:38, April 4, 2013 (UTC)

Unfortunately this doesn't handle equality correctly, but it's easy to fix:

0 1 * l 0
0 _ * r 1
1 1 _ r 2
1 _ _ r 6
2 1 * r 2
2 _ * r 3
3 1 * r 3
3 _ * l 4
4 1 _ l 5
4 _ > l halt
5 1 * l 5
5 _ * l 0
6 _ = l halt
6 1 < l halt

Deedlit11 (talk) 02:59, April 5, 2013 (UTC)

FB100Z's answer

0 1 * r *
0 _ * r r2
r2 1 * r *
r2 _ * l r3
r3 1 _ l l1
r3 _ * * halt

l1 1 * l *
l1 _ * l l2
l2 1 * l *
l2 _ * l l3
l3 1 _ r 0
l3 _ * * halt

I'm not sure if this counts.

FB100Ztalkcontribs 03:26, April 4, 2013 (UTC)

LittlePeng9's answer

; Output is a character under scanning head after halting
0 1 1 r 0
0 _ > r 1
1 < > r 1
1 1 < l 2
1 _ _ l 3
2 > < l 2
2 1 > r 1
2 _ _ r halt
3 > _ l 3
3 _ = * halt
3 1 > * halt

First of three to succesfully determine equality. As we need symbols to write output anyway, I used them for execution.

LittlePeng9 (talk) 16:21, April 4, 2013 (UTC)

Duplication

Given \(n\), output two copies of \(n\).

Ikosarakt's answer

0 _ _ l halt
0 1 _ r 1
1 1 * r 1
1 _ * r 2
2 _ 1 r 3
2 1 * r 2
3 _ 1 l 4
4 _ * l 5
4 1 * l 4
5 _ * r 0
5 1 * l 5

Ikosarakt1 (talk ^ contribs) 07:41, April 4, 2013 (UTC)

LittlePeng9's answer

; Output is two copies of input with blank inbetween
0 1 _ r 1
0 _ _ r halt
1 1 1 r 1
1 _ _ r 2
2 1 1 r 2
2 _ 1 l 3
3 1 1 l 3
3 _ _ l 4
4 1 1 l 4
4 _ 1 r 0

4-state machine

0 1 _ l 1
0 _ _ l halt
1 _ 1 l 2
2 _ 1 r 3
2 1 1 l 2
3 1 1 r 3
3 _ _ r 0

3-state machine

0 1 _ l 1
0 _ _ l halt
1 _ 1 r 2
1 1 1 l 1
2 1 1 r 2
2 _ 1 r 0

1-state, 3-color machine - input is n 1's followed by x

0 _ 1 r 0
0 1 _ l 0
0 x _ l halt

LittlePeng9 (talk) 15:36, April 4, 2013 (UTC)

Ikosarakt's answer

0 _ 1 r 1
0 1 _ r 0
1 1 1 r 0
1 _ 1 r halt

Input form is n 1's, each separated by one space.Ikosarakt1 (talk ^ contribs) 17:04, May 2, 2013 (UTC)

Triple the number

Input is \(n\), output is \(3n\)

Wythagoras's answer

0 1 _ l 1
0 _ _ r halt
1 1 1 l 1
1 _ 1 l 2
2 _ 1 r 3
3 1 1 r 3
3 _ 1 r 0

LittlePeng9's answer

Binary, input and output must be written backwards.

0 0 0 r 0
0 1 1 r 1
0 _ _ l halt
1 _ 1 r 0
1 0 1 r 0
1 1 0 r 2
2 _ 0 r 1
2 0 0 r 1
2 1 1 r 2

LittlePeng9 (talk) 17:11, September 17, 2013 (UTC)

Binary counter

Make a binary counter that repeatedly increments number in binary radix (this machine shouldn't halts).

Ikosarakt's answer

0 _ _ l 1
0 1 _ r 0
1 _ 1 r 0
1 1 1 l 1

I believe this is one of the simpliest Turing machines that can do it. Ikosarakt1 (talk ^ contribs) 18:37, May 1, 2013 (UTC)

Proof for the simplest machine

Since binary counter must be able to start with blank, 1-state Turing machine that able to do it is impossible, since we know that if it doesn't halts after the very first step, it falls into the most trivial infinite loop.

Palindrome

Test whether an input is a palindrome.

FB100Z's answer

This is a Python script that creates a Turing machine. Handles up to 10 symbols.

n = 10

print('0 * * * read')
print('read _ P * halt')
for i in range(n):
    print('read {0} _ r gr{0}'.format(i))

for i in range(n):
    print('gr{0} _ * l chk{0}'.format(i))
    print('gr{0} * * r *'.format(i))

for i in range(n):
    print('chk{0} _ P * halt'.format(i))
    print('chk{0} {0} _ l gl'.format(i))
    print('chk{0} * N * halt'.format(i))

print('gl _ * r read')
print('gl * * l *'.format(i))

The number of states is 2c + 2.

My main motivation for this is the Lychrel problem. FB100Ztalkcontribs 19:42, April 14, 2013 (UTC)

LittlePeng9's answer

To check if finite string of positive integers is palindrome, replace each integer n with string of n 1's and blanks every two integers. Character under halted head is answer.

0 1 1 r 0
0 _ y r 1
1 1 1 r 0
1 _ _ l 2
2 y _ l 3
3 1 _ l 4
3 y _ l 6
4 * * l 4
4 _ _ r 5
5 1 _ r 8
5 y _ * halt
6 * * l 6
6 _ _ r 7
7 y _ r 8
7 1 _ * halt
8 * * r 8
8 _ _ l 3
* _ 1 * halt

Alternatively, piece of C++ code creating set of transitions for any set of characters:

#include<conio.h>
#include<fstream>
using namespace std;

ofstream outFile("palindrome.txt");

int main(){
	outFile<<"1 * * l 1"<<endl<<"1 _ _ r 0"<<endl<<"0 _ 1 * halt"<<endl;
	char c=getche();
	while(c!=13){
		outFile<<"0 "<<c<<" _ r "<<c<<"0"<<endl;
		outFile<<c<<"0 * * r *"<<endl;
		outFile<<c<<"0 _ _ l "<<c<<"1"<<endl;
		outFile<<c<<"1 "<<c<<" _ l 1"<<endl;
		outFile<<c<<"1 _ 1 * halt"<<endl;
		outFile<<c<<"1 * _ * halt"<<endl;
		c=getche();
	}
	return 0;
}

Just type in characters you want. They can repeat, but you must be sure if simulator accepts them. To finish press Enter. LittlePeng9 (talk) 20:14, April 14, 2013 (UTC)

Googleaarex's answer

0 * * r 0a
0a * * r 0a
0 x 1 l 4a
0 y 0 l 4a
0 _ _ l 1
0a _ _ l 1
1 x x l 1
1 y y l 1
1 1 x l 2.1
1 0 y l 2.0
2.1 * * l 2.1
2.1 x 1 r 3.1
2.1 y 0 r 3.1
2.1 _ _ r 3.1
3.1 x 1 r 4a
3.1 y 0 r 4r
3.1 1 x r 0
3.1 0 0 r 4r
2.0 * * l 2.0
2.0 _ _ r 3.0
2.0 x 1 r 3.0
2.0 y 0 r 3.0
3.0 y 0 r 4a
3.0 x 1 r 4r
3.0 1 1 r 4r
3.0 0 y r 0
4a x 1 r 4a
4a y 0 r 4a
4a * * r 4a
4a _ _ * halt-accept
4r x 1 r 4r
4r y 0 r 4r
4r * * r 4r
4r _ _ * halt-reject

Separating row

Given a row of non-zeros, separate all symbols by the space.

LittlePeng9's answer

Case where only symbol is 1:

0 1 _ l 1
0 _ _ r 2
1 _ 1 l 0
2 _ * r halt
2 1 1 r 3
3 _ _ r 2
3 1 1 l 0

C++ program solving general case - type all symbols you want. Press enter to end.

#include<conio.h>
#include<fstream>
using namespace std;

ofstream outFile("separate.txt");

int main(){
	outFile<<"0 _ _ r 1"<<endl<<"1 _ _ l halt"<<endl<<"1 * * r 2"<<endl<<"2 _ _ r 1"<<endl<<"2 * * l 0"<<endl;
	char c=getche();
	while(c!=13){
		outFile<<c<<"0 _ "<<c<<" l 0"<<endl;
		outFile<<"0 "<<c<<" _ l "<<c<<"0"<<endl;
		c=getche();
	}
	return 0;
}

LittlePeng9 (talk) 17:45, May 11, 2013 (UTC)

#include<conio.h>
#include<fstream>
using namespace std;

ofstream outFile("separate.txt");

int main(){
	outFile<<"0 _ _ r 1"<<endl<<"1 _ _ l halt"<<endl<<"1 * * r 2"<<endl<<"2 _ _ r 1"<<endl<<"2 * * l 0"<<endl;
	char c=getche();
	while(c!=13){
		outFile<<c<<"0 _ "<<c<<" l 0"<<endl;
		outFile<<"0 "<<c<<" _ l "<<c<<"0"<<endl;
		c=getche();
	}
	return 0;
}

Mirror sequence

Given string of separated rows, compute its mirror string (e.g. 1 1111 11 111 11 mirrors to 11 111 11 1111 1).

LittlePeng9's answer

0 1 x r 0
0 _ y r 1
1 1 x r 0
1 _ _ l 2
2 y | l 3
3 x 1 r 5
3 y _ r 7
3 1 1 l 3
3 _ _ l 4
4 1 1 l 3
4 x 1 r 5
4 y _ r 5
4 _ _ r 10
5 * * r 5
5 | | r 6
6 * * r 6
6 _ x l 9
7 * * r 7
7 | | r 8
8 * * r 8
8 _ y l 9
9 * * l 9
9 | | l 3
10 * _ r 10
10 | _ r 11
11 x 1 r 11
11 y _ r 11
11 _ _ l halt

LittlePeng9 (talk) 18:10, May 11, 2013 (UTC)

Number ordering

Given a sequence of numbers, order them by their value.

LittlePeng9's answer

0 1 x r 1
0 _ _ r 11
1 1 1 r 1
1 _ _ r 2
2 1 1 r 2
2 * * l 3
3 1 x l 4
3 _ x l 6
4 1 1 l 4
4 x 1 r 4
4 _ _ l 5
5 1 1 l 5
5 * * r 0
6 1 x l 6
6 x _ r 7
7 x 1 r 7
7 _ _ l 8
8 * 1 l 8
8 _ _ l 9
9 * 1 l 8
9 _ _ r 10
10 _ _ r 0
11 * 1 r 11
11 _ _ r 12
12 1 1 l 4
12 _ _ l 13
13 _ _ l 14
13 * 1 l 13
14 * 1 l 13
14 _ _ r halt

LittlePeng9 (talk) 16:59, May 24, 2013 (UTC)

Cube the number

Compute \(a^3\).

LittlePeng9's answer

Uses my powers machine.

0 1 1 l s1
0 _ _ r halt
s1 _ _ l s2
s2 _ 1 l s3
s3 _ 1 l s4
s4 _ 1 l 0a

0a _ x r 0b
0b 1 _ r 1
1 1 _ r 21
1 _ _ r 10
1 x _ r 11
2 * * r 2
2 _ _ r 3
3 1 _ r 4
3 x _ l 8
4 1 1 r 4
4 _ x r 5
4 x x r 5
5 1 1 r 5
5 _ 1 l 6
6 1 1 l 6
6 * * l 7
7 1 1 l 7
7 _ 1 r 3
8 1 1 l 8
8 x x l 8
8 _ x l 9
9 1 1 l 8
9 _ _ r 10
10 x _ r 1
10 1 1 l 20
11 1 1 r 11
11 x _ r 11
11 _ _ l 12
12 1 1 l 12
12 _ _ r m0
m0 1 _ r m1
m0 _ _ r m9
m1 1 1 r m1
m1 _ _ r m2
m2 1 _ r m3
m2 _ _ l m7
m3 1 1 r m3
m3 _ _ r m4
m4 1 1 r m4
m4 _ 1 l m5
m5 1 1 l m5
m5 _ _ l m6
m6 1 1 l m6
m6 _ 1 r m2
m7 1 1 l m7
m7 _ _ l m8
m8 1 1 l m8
m8 _ _ r m0
m9 1 _ r m9
m9 _ 1 r 13
13 1 1 r 13
13 _ _ l 14
14 1 _ l 15
15 1 1 l 15
15 _ 1 l 16
16 1 1 r 17
16 _ _ r 13
16 x _ r 18
17 1 _ l 12
18 1 _ r halt
19 1 _ r 19
19 _ 1 r halt
20 * * l 20
20 x _ r halt
21 * * r 2
21 _ x r 3

LittlePeng9 (talk) 09:15, April 6, 2014 (UTC)

Primarily test

Test whether entered number is a prime or not.

LittlePeng9's answer

0 1 1 l 0
0 _ _ l 1
1 _ 1 l 9
2 1 1 r 2
2 x x l 2
2 _ _ l 3
3 x x l 3
3 1 x r 4
3 _ _ r 6
4 x x r 4
4 _ _ r 5
5 x x r 5
5 1 x l 2
5 _ _ l 8
6 * 1 r 6
6 _ _ r 7
7 x x r 7
7 1 1 l 2
7 _ _ l 10
8 x 1 l 8
8 _ _ l 9
9 * 1 l 9
9 _ 1 r 2

10 x _ l 11
10 _ 1 * halt
11 * * l 11
11 _ _ l 12
12 * * l 12
12 _ _ r 13
13 1 _ r 6
13 _ _ l halt

Two color variant

0 1 1 l s1
s1 _ _ l s2
s2 _ 1 l s3
s3 _ _ l 1
s0 1 _ l 1
s0 _ 1 r 10
1 _ 1 r 2
2 _ _ r 3
3 1 1 r 3
3 _ _ r 4
4 1 1 r 4
4 _ _ l 5
5 1 _ r 6
5 _ 1 l 15
6 _ 1 l 7
7 _ _ l 8
8 1 1 l 8
8 _ _ l 9
9 1 1 l 9
9 _ _ r s0
10 _ 1 r 14
10 1 1 l 11
11 1 _ l 11
11 _ 1 l 12
12 1 1 l 12
12 _ _ r 13
13 1 _ r s0
14 1 1 r 14
14 _ _ l 18
15 1 1 l 15
15 _ 1 l 16
16 1 1 l 16
16 _ _ r 17
17 1 _ r s0
18 1 _ l 19
19 1 _ l c4

c0 1 1 l c0
c0 _ _ r c1
c1 1 _ r c2
c1 _ _ r c6
c2 1 1 r c2
c2 _ _ r c3
c3 1 1 r c3
c3 _ _ l c4
c4 1 _ l c5
c4 _ 1 r halt
c5 1 1 l c5
c5 _ _ l c0
c6 1 _ r c6
c6 _ _ r halt

LittlePeng9 (talk) 11:07, April 7, 2013 (UTC)

Factorial

Compute \(n!\) given \(n\).

Ikosarakt's answer

0 _ 1 r halt
0 1 _ r 50
1 1 * r 1
1 _ * r 2
2 _ * r 3
3 _ 1 l 4
3 1 * r 3
4 _ * l 5
4 1 * l 4
5 _ * l 6
6 _ 1 r 7
6 1 * l 6
7 1 _ r 1
7 _ 2 l 8
8 2 * l 8
8 1 * l 8
8 _ * r 9
9 1 _ r 10
9 2 _ r halt
10 1 _ r 11
10 2 * r 40
11 1 * r 11
11 2 * r 11
11 _ * r 12
12 _ * r 12
12 1 * r 13
13 1 * r 13
13 _ * r 14
14 1 * r 14
14 _ 1 l 15
15 _ * l 16
15 1 * l 15
16 1 * l 16
16 _ * l 45
17 2 * l 17
17 1 * l 17
17 _ 1 r 10
18 _ * r 46
18 1 _ r 33
19 1 * r 19
19 _ * r 20
20 _ * l 25
20 1 * r 28
21 1 * r 21
21 _ * r 22
22 _ 1 l 23
22 1 * r 22
23 _ * l 24
23 1 * l 23
24 1 * l 24
24 _ 1 r 32
25 1 * l 25
25 _ * l 26
26 1 * l 25
26 _ * r 27
27 _ * r 18
28 1 * r 28
28 _ * r 29
29 1 * r 28
29 _ * l 30
30 _ * l 31
31 1 * l 31
31 _ * r 32
32 1 _ r 21
32 _ * l 25
33 _ * r 34
33 1 * r 19
34 _ * r halt
34 1 _ r 35
35 1 * r 35
35 _ 1 r 36
36 _ * r 37
36 1 * r 36
37 _ * l 41
37 1 * l 38
38 _ * l 39
39 1 * l 39
39 _ * r 34
40 _ * r 18
41 _ * l 42
42 1 * l 42
42 _ * l 43
43 _ * l 43
43 2 * l 44
44 1 * l 47
44 _ * r 9
45 _ * l 45
45 2 * l 17
46 _ * r 46
46 1 _ r 33
47 _ * r 49
47 1 * l 48
48 1 * l 48
48 _ * r 9
49 1 _ r 49
49 2 _ r halt
50 _ 1 l halt
50 1 * r 1

LittlePeng9's answer

If we allow it to not handle number 1 (and no else), we can to replace x0 with 1, so state x0 will never be used.

Edit: further reduced by 1 state

; First part of setup
0 _ 1 r halt
0 1 1 r x0
1 _ _ l 2
1 1 1 l 1
2 _ 1 r 3
3 _ _ r s0
; We must check if n is 1, if it is, machine runs infinitely
x0 _ _ l halt
x0 1 1 l 1
; Second part of setup. This is my string duplication machine
s0 1 _ r s1
s0 _ _ r 4
s1 1 1 r s1
s1 _ _ r s2
s2 1 1 r s2
s2 _ 1 l s3
s3 1 1 l s3
s3 _ _ l s4
s4 1 1 l s4
s4 _ 1 r s0
; After duplication we have to delete 1 from second string
4 1 1 r 4
4 _ _ l 5
5 1 _ l 6
5 _ _ l 7 ; If smaller string is 1, we end setup
6 1 1 l 6
6 _ _ r s0 ; Then we duplicate

7 _ _ l 8
8 1 1 l 9
8 _ 1 l halt
9 _ _ l 10
10 1 1 l 10
10 _ _ r m0

m0 1 _ r m1
m1 1 1 r m1
m1 _ _ r m2
m2 _ _ r m2
m2 1 _ r m3
m3 1 1 r m4
m3 _ _ r m9
m4 1 1 r m4
m4 _ _ r m5
m5 1 1 r m5
m5 _ 1 l m6
m6 1 1 l m6
m6 _ _ l m7
m7 _ _ l m7
m7 1 1 l m8
m8 1 1 l m8
m8 _ _ r m2
m9 1 1 r m9
m9 _ 1 l m10
m10 1 1 l m10
m10 _ _ l m11
m11 _ 1 l m11
m11 1 1 r m12
m12 1 _ l m13
m13 1 1 l m14
m14 1 1 l m15
m14 _ _ r m16
m15 1 1 l m15
m15 _ _ r m0
m16 1 _ r m16
m16 _ _ r m17
m17 _ _ r m17
m17 1 _ r m18
m18 1 1 r m18
m18 _ 1 l 11

11 1 1 l 11
11 _ _ l 12
12 1 1 l 13
12 _ _ r 14
13 1 1 r 10
13 _ _ r 17
14 _ 1 r 15
15 1 1 r 15
15 _ _ l 16
16 1 _ l 11

17 1 _ r halt

LittlePeng9 (talk) 15:50, April 5, 2013 (UTC)

Improved version

Based on my not-so-new 10-state multiplication machine.

; First part of setup
0 _ 1 r halt
0 1 1 r x0
1 _ _ l 2
1 1 1 l 1
2 _ 1 r 3
3 _ _ r s0
; We must check if n is 1, if it is, machine runs infinitely
x0 _ _ l halt
x0 1 1 l 1
; Second part of setup. This is my string duplication machine
s0 1 _ r s1
s0 _ _ r 4
s1 1 1 r s1
s1 _ _ r s2
s2 1 1 r s2
s2 _ 1 l s3
s3 1 1 l s3
s3 _ _ l s4
s4 1 1 l s4
s4 _ 1 r s0
; After duplication we have to delete 1 from second string
4 1 1 r 4
4 _ _ l 5
5 1 _ l 6
5 _ _ l 7 ; If smaller string is 1, we end setup
6 1 1 l 6
6 _ _ r s0 ; Then we duplicate

7 _ _ l 8
8 1 1 l 9
8 _ 1 l halt
9 _ _ l 10
10 1 1 l 10
10 _ _ r m0

m0 1 _ r m1
m0 _ _ r m9
m1 1 1 r m1
m1 _ _ r m2
m2 1 _ r m3
m2 _ _ l m7
m3 1 1 r m3
m3 _ _ r m4
m4 1 1 r m4
m4 _ 1 l m5
m5 1 1 l m5
m5 _ _ l m6
m6 1 1 l m6
m6 _ 1 r m2
m7 1 1 l m7
m7 _ _ l m8
m8 1 1 l m8
m8 _ _ r m0
m9 1 _ r m9
m9 _ 1 r 15

11 1 1 l 11
11 _ _ l 12
12 1 1 l 13
12 _ _ r 14
13 1 1 r 10
13 _ _ r 17
14 _ 1 r 15
15 1 1 r 15
15 _ _ l 16
16 1 _ l 11

17 1 _ r halt

LittlePeng9 (talk) 17:35, May 4, 2015 (UTC)

Polynomial

Given a sequence \(a_0, a_1, a_2, \ldots, a_n\) and an input \(x\), compute \(\sum_{i = 0}^n a_nx^n\); i.e. the polynomial with coefficients \(a_i\) and input \(x\).

LittlePeng9's answer

The input is of the following form: 11...1|11...1 11...1 ... 11...1| where first block has \(x\) 1's, and successive blocks have \(a_n,...,a_2,a_1,a_0\) 1's, respectively. The machine only works for positive input and coefficients.

0 1 1 l 1
1 _ | r 2
2 1 _ l 3
2 | | l 5
3 * * l 3
3 _ 1 r 4
4 * * r 4
4 _ 1 r 2
5 1 1 l 5
5 | _ l 6
6 1 _ l 7
7 1 1 l 7
7 _ 1 r 8
8 1 1 r 8
8 _ | r 9
9 * * r 9
9 | _ r 10
10 1 1 r 10
10 _ | l M0
10 | _ l 17 !

M0 1 _ l M1
M0 _ _ l M9
M1 1 1 l M1
M1 _ _ l M2
M2 1 _ l M3
M2 _ _ r M7
M3 1 1 l M3
M3 _ _ l M4
M4 1 1 l M4
M4 | 1 l M4'
M4' 1 | l M4
M4 _ 1 r M5
M5 * * r M5
M5 _ _ r M6
M6 1 1 r M6
M6 _ 1 l M2
M7 1 1 r M7
M7 _ _ r M8
M8 1 1 r M8
M8 _ _ l M0
M9 1 _ l M9
M9 _ _ l 12

11 1 1 r 11
11 _ 1 l 12
11 | 1 l 16
12 * * l 12
12 _ _ r 13
13 1 _ r 14
14 1 1 r 14
14 | 1 r 15
15 1 | r 11
16 * * l 16
16 _ _ r 0

17 1 1 l 17
17 _ _ l 18
18 * _ l 18
18 | _ l 19
19 1 _ l 19
19 _ _ r halt

LittlePeng9 (talk) 17:19, May 4, 2015 (UTC)

Googolplex

Compute googolplex.

LittlePeng9's answer

Returns decimal expansion of googolplex

0 _ 1 r 1
1 _ 0 r 2
2 _ 0 r 3

3 9 9 l 3
3 _ _ l 4
4 0 9 l 4
4 1 0 r 5
4 2 1 r 5
4 3 2 r 5
4 4 3 r 5
4 5 4 r 5
4 6 5 r 5
4 7 6 r 5
4 8 7 r 5
4 9 8 r 5
4 _ _ r 7
4 x _ r 8
5 * * r 5
5 _ _ r 6
6 9 9 r 6
6 _ 9 l 3

7 9 _ r 7
7 _ x r 5
8 9 _ r 8
8 _ 1 r 9
9 9 0 r 9
9 _ _ l halt

LittlePeng9 (talk) 18:34, April 6, 2014 (UTC)

Googleaarex's answer

0 _ 1 r a1
a1 _ 0 r a2
a2 _ 0 r a3
a3 _ _ r b1

b1 _ 1 l b2
b2 1 0 l b2
b2 0 0 l b2
b2 _ _ l c1

c1 0 9 l c1
c1 1 0 r c2
c1 2 1 r c2
c1 3 2 r c2
c1 4 3 r c2
c1 5 4 r c2
c1 6 5 r c2
c1 7 6 r c2
c1 8 7 r c2
c1 9 8 r c2
c1 _ _ r d1
c1 x _ r e1
c2 _ _ r c3
c2 * * r c2
c3 _ 0 l c4
c3 * * r c3
c4 _ _ l c1
c4 * * l c4

d1 9 _ r d1
d1 _ x r d2
d2 1 1 r d2
d2 0 0 r d2
d2 _ _ r d3
d3 _ 1 l b2

e1 9 _ r e1
e1 _ _ * halt

AarexTiaokhiao 20:24, April 6, 2014 (UTC)

Coins in boxes

Cite from A. P. Goucher's blog:

There are two different operations you’re allowed to do: Remove a coin from box i and add two coins to box i + 1. Remove a coin from box i and swap the contents of boxes i + 1 and i + 2.

Compute the largest number obtainable from any possible expression with these rules and arbitrary number of boxes.

Grangol

Compute Grangol.

Cloudy176's answer

This machine starts with 2 and calculates 10^X 101 times. It is based on LittlePeng9's googolplex machine.

0 _ # r 1
1 _ 1 r 2
2 _ 0 r 3
3 _ 0 r 4
4 _ _ r 5
5 _ 2 r d0

d0 9 9 l d0
d0 _ _ l d1
d1 0 9 l d1
d1 1 0 r d2
d1 2 1 r d2
d1 3 2 r d2
d1 4 3 r d2
d1 5 4 r d2
d1 6 5 r d2
d1 7 6 r d2
d1 8 7 r d2
d1 9 8 r d2
d1 _ _ l e0
d2 * * r d2
d2 _ _ r d3
d3 9 9 r d3
d3 _ 9 l d0

e0 _ _ l e0
e0 0 9 l e0
e0 1 0 r e1
e0 2 1 r e1
e0 3 2 r e1
e0 4 3 r e1
e0 5 4 r e1
e0 6 5 r e1
e0 7 6 r e1
e0 8 7 r e1
e0 9 8 r e1
e0 # _ r f0
e1 * * r e1
e1 _ _ r e2
e2 _ _ r e2
e2 9 _ r e3
e3 9 _ r e3
e3 _ _ r d2

f0 9 _ r f0
f0 _ _ r f1
f1 _ _ r f1
f1 9 _ r f2
f2 9 _ r f2
f2 _ _ r f3
f3 _ _ r f3
f3 9 1 r f4
f4 9 0 r f4
f4 _ 0 r halt

— ☁ I want more clouds! ⛅ 00:50, April 8, 2014 (UTC)

Prime factorization

Given \(n\), factor \(n\).

LittlePeng9's answer

0 1 1 l 1
1 _ _ l 2
2 _ 1 l 3
3 _ 1 r 4
4 1 1 r 4
4 _ _ l 5

5 x x l 5
5 1 x r 6
5 _ _ r 9
6 x x r 6
6 _ _ r 7
7 x x r 7
7 y y r 7
7 1 x l 8
7 _ _ l 27
8 x x l 8
8 y y l 8
8 _ _ l 5

9 x 1 r 9
9 _ _ r 10
10 x x r 10
10 y y r 10
10 1 1 l 11
10 _ _ l 12
11 x y l 8

12 x 1 l 13
13 y 1 l 13
13 1 1 l 13
13 x 1 r 14
13 _ y l 16
14 1 1 r 14
14 _ _ l 15
15 1 _ l 13

16 1 x l 17
16 x x l 16
16 _ _ l 21
17 1 1 l 17
17 _ _ l 18
18 1 1 l 17
18 _ x r 20
18 x x l 19
19 x x l 19
19 _ x r 20
20 * * r 20
20 y y l 16

21 * * l 21
21 x x l 22
22 x x l 22
22 _ _ r 23
23 x 1 r 23
23 * * r 23
23 y _ r 24
24 1 1 r 25
25 1 1 l 26
25 _ _ l 31
26 1 1 l 4

27 * 1 l 27
27 _ y l 28
28 * 1 l 28
28 _ 1 l 29
29 1 _ l 28
29 _ _ r 30
30 * * r 30
30 y _ l 5

31 1 _ l 31
31 _ _ l 32
32 1 _ l 32
32 _ _ l halt

LittlePeng9 (talk) 18:54, April 4, 2013 (UTC)

Ackermann function

Compute Ackermann function (there are many variations of it, on your choice).

LittlePeng9's answer

Standard Ackermann function A(m,n) (works even for any argument 0). It utilizes my restricted up-arrow notation.

0 1 1 l 1
0 _ 1 l halt
1 _ 1 r 2
2 1 ^ r 2
2 _ 1 r 3
3 1 1 r 3
3 _ 1 l a1
4 1 _ r 5
5 1 _ r halt

a0 * * r a0
a0 _ _ l a1
a1 1 1 l a1
a1 ^ 1 l a1a
a1 _ _ r 4
a1a 1 1 r a1 
a1a ^ ^ r a1b
a1b * * r a2
a2 _ * l a1
a2 1 _ l a3
a3 1 1 l a3
a3 ^ y r a4
a4 * * r a4
a4 1 1 r a5
a5 ^ ^ r a5
a5 _ ^ r a6
a6 1 _ r a7
a6 _ _ l a11
a7 1 1 r a7
a7 _ 1 l a8
a8 * * l a8
a8 y y l a9
a9 y y l a9
a9 ^ y r a4
a9 1 1 r a10
a10 y ^ r a10
a10 _ ^ r a0
a10 * * r a10
a11 1 _ l a12
a11 ^ _ l a11
a12 * _ l a12
a12 1 1 r a13
a13 _ 1 r a14
a14 _ 1 l a1

Friedman's one argument \(A(n)=2\uparrow^{n-1}n\)

0 1 _ r 1
0 _ ^ r 5
1 1 1 r 1
1 _ _ r 2
1 ^ _ r halt
2 1 1 r 2
2 _ 1 l 3
3 1 1 l 3
3 _ _ l 4
3 ^ ^ l 0
4 1 1 l 4
4 _ 1 r 0

5 * ^ l 5
5 _ _ r 6
6 ^ 1 r a0
6 1 _ l 6
6 _ _ l 6

a0 * * r a0
a0 _ _ l a1
a1 1 1 l a1
a1 ^ 1 l a1a
a1 _ 1 l halt
a1a 1 1 r a1 
a1a ^ ^ r a1b
a1b * * r a2
a2 * _ l a3
a2 _ _ l 2
a3 1 1 l a3
a3 ^ y r a4
a4 * * r a4
a4 1 1 r a5
a5 ^ ^ r a5
a5 _ ^ r a6
a6 1 _ r a7
a6 _ _ l a11
a7 1 1 r a7
a7 _ 1 l a8
a8 * * l a8
a8 y y l a9
a9 y y l a9
a9 ^ y r a4
a9 1 1 r a10
a10 y ^ r a10
a10 _ ^ r a0
a10 * * r a10
a11 1 _ l a12
a11 ^ _ l a11
a12 * _ l a12
a12 1 1 r a13
a13 _ 1 r a14
a14 _ 1 l a1

LittlePeng9 (talk) 18:33, May 11, 2013 (UTC)

Up-arrow notation

Compute an arbitrary expression in the up-arrow notation.

LittlePeng9's answer

In expression of form \(a\uparrow^m b\uparrow^n c...\) replace each number with corresponding string of 1's and each \(\uparrow^p\) replace with p+2 up-arrows. Right associative.

0 * * r 0
0 _ _ l 1
1 1 _ l 2
2 ^ _ l 3
2 1 1 l 4
3 ^ _ l 3
3 1 _ l 2
4 1 1 l 4
4 ^ 1 l 4'
4 _ 1 l halt
4' ^ ^ l 5
4' 1 1 r 0
5 ^ ^ l 5
5 1 1 r 6
6 ^ x r 7
6 1 y r 9
6 | ^ l 12
7 * * r 7
7 _ | r 8
7 | | r 8
8 * * r 8
8 _ ^ l 11
9 * * r 9
9 | | r 10
10 * * r 10
10 _ 1 l 11
11 * * l 11
11 x ^ r 6
11 y 1 r 6
12 * * l 12
12 ^ ^ l 12'
12' ^ ^ l 12'
12' * * l 13
12' 1 x r 14
13 * * l 13
13 ^ ^ r 20
13 _ _ r 20
13 1 x r 14
14 * * r 14
14 ^ ^ r 15
15 ^ ^ r 15
15 x x r 16
15 1 x l 12
16 x x r 16
16 1 x l 12
16 ^ x r 17
17 ^ ^ r 17
17 1 ^ r 18
18 ^ 1 r 17
18 1 1 r 18
18 _ 1 l 19
19 * * l 19
19 x x l 12
20 x 1 r 20
20 ^ ^ r 21
21 ^ ^ r 21
21 x x r 22
22 x x r 22
22 1 _ r 23
22 ^ ^ l 30
23 1 _ r 23
23 ^ ^ l 24
24 _ ^ r 25
25 ^ ^ r 25
25 1 1 l 26
26 ^ 1 r 27
27 1 1 r 27
27 _ _ l 28
28 1 _ l 29
29 * * l 29
29 _ ^ r 25
29 x 1 l 30
30 x 1 l 30
30 ^ ^ r 31
31 * * r 31
31 _ _ l 32
32 1 _ l 1

Graham's number

Compute Graham's number. The score limit is 10000 — no TMs with \(g_{64}\) states!

LittlePeng9's answer

Clickity click ! LittlePeng9 (talk) 18:07, April 16, 2013 (UTC)

Steinhaus-Moser notation

Compute an arbitrary expression in Steinhaus-Moser notation.

LittlePeng9's answer

To compute m in n-gon, write n 1's followed by a blank and m 1's.

0 1 1 r 0
0 _ _ r 1
1 1 1 r 0
1 _ _ l 2
2 _ _ l 3A
3A 1 1 l 3B
3B 1 1 l 3
3B _ _ l 40
3 1 1 l 3
3 _ _ l 4
4 _ _ r halt
4 1 1 l 5
5 _ _ r 6
5 1 1 r 16
6 1 1 r 6
6 _ 1 r 7
7 1 1 r 7
7 _ _ l 8
8 1 _ l 9
9 1 _ l 10
10 1 x r 11
10 _ _ r E0
11 * * r 11
11 _ _ r 12
12 1 1 r 12
12 _ 1 l 13
13 * * l 13
13 x 1 l 10

E0 1 1 l E0a
E0 _ _ r E19
E0a _ x r E0b
E0b 1 _ r E1
E1 1 _ r E21
E1 _ _ r E10
E1 x _ r E11
E2 * * r E2
E2 _ _ r E3
E3 1 _ r E4
E3 x _ l E8
E4 1 1 r E4
E4 _ x r E5
E4 x x r E5
E5 1 1 r E5
E5 _ 1 l E6
E6 1 1 l E6
E6 * * l E7
E7 1 1 l E7
E7 _ 1 r E3
E8 1 1 l E8
E8 x x l E8
E8 _ x l E9
E9 1 1 l E8
E9 _ _ r E10
E10 x _ r E1
E10 1 1 l E20
E11 1 1 r E11
E11 x _ r E11
E11 _ _ l E12
E12 1 1 l E12
E12 _ _ r Em0
Em0 1 _ r Em1
Em0 _ _ r Em9
Em1 1 1 r Em1
Em1 _ _ r Em2
Em2 1 _ r Em3
Em2 _ _ l Em7
Em3 1 1 r Em3
Em3 _ _ r Em4
Em4 1 1 r Em4
Em4 _ 1 l Em5
Em5 1 1 l Em5
Em5 _ _ l Em6
Em6 1 1 l Em6
Em6 _ 1 r Em2
Em7 1 1 l Em7
Em7 _ _ l Em8
Em8 1 1 l Em8
Em8 _ _ r Em0
Em9 1 _ r Em9
Em9 _ 1 r E13
E13 1 1 r E13
E13 _ _ l E14
E14 1 _ l E15
E15 1 1 l E15
E15 _ 1 l E16
E16 1 1 r E17
E16 _ _ r E13
E16 x _ r E18
E17 1 _ l E12
E18 1 1 r 14
E19 1 _ r E19
E19 _ 1 r halt
E20 * * l E20
E20 x _ r halt
E21 * * r E2
E21 _ x r E3

14 1 1 r 14
14 _ _ l 15
15 1 _ l 3

16 1 1 r 16
16 _ _ r 17
17 1 1 r 17
17 _ x l 18
18 1 _ r 19
18 _ _ l 21
19 * * r 19
19 _ 1 l 20
20 * * l 20
20 _ 1 l 18
21 1 x r 22
22 _ _ r 23
23 * * r 23
23 _ _ l 24
24 1 _ l 25
25 1 1 l 26
25 x _ l 38
26 * * l 26
26 x x l 27
27 * * l 27
27 x x l 28
28 1 _ r 29
28 _ _ r 36
29 * * r 29
29 _ 1 r 30
30 1 _ r 31
31 1 1 r 31
31 x 1 r 32
31 _ 1 l 33
32 1 x r 31
33 * * l 33
33 x x l 34
34 * * l 34
34 x x l 35
35 1 1 l 35
35 _ 1 l 28
35 x _ r 37
36 * * r 36
36 _ x r 30
37 * * r 37
37 _ _ r 23
38 1 _ l 39
39 * 1 l 39
39 x _ r 0

40 1 _ l 40
40 _ _ l 41
41 1 _ l 40
41 _ _ r halt

LittlePeng9 (talk) 16:42, May 4, 2015 (UTC)

PRNG

Construct any pseudo-random number generator. Open problem, no scores here.

LittlePeng9's answer

; Input is arbitrary number written in binary
; Output is a lot of mess. Let say it's the number to the right of 's'
0 1 0 r 1
0 0 _ r 1
0 _ 1 r 1
1 1 _ r 2
1 0 1 r 2
1 _ 0 r 2
2 1 0 r 3
2 0 1 r 2
3 1 0 r 2
3 0 1 r 3
2 _ s l 6
3 _ s l 6
0 s s r halt
1 s s r 5
2 s s r 4
3 s s r 5
4 _ 0 l 6
5 _ 1 l 6
6 _ 0 r 0
4 * * r 4
5 * * r 5
6 * * l 6

I'm not even sure if this machine always halts! But if it does, it seems pretty random.

LittlePeng9 (talk) 17:08, April 4, 2013 (UTC)

Base converter

Given a number in specified base, and base in which the number should be converted, compute it

LittlePeng9's answer

Say we have number written in base n. For every digit a of input number create block 11...100...0 with a 1's such that block has length n-1. Between every block place x. After that place a blank and then m-1 0's, where m is output base. Output is same format as first part of input, but with digits in reverse order. Just count number of 1's in a block to get a digit. You can use it for mixed bases, too.

0 * * r 0
0 _ _ l 1
1 0 1 l 1
1 1 0 r 2
1 x x l 1
1 _ _ r 13
2 1 0 r 2
2 x x r 3
2 _ _ r 4
3 * * r 3
3 _ _ r 4
4 1 0 r 4
4 0 1 l 5
4 x x r 4
4 _ x l 7
5 0 1 l 5
5 x x l 6
5 _ _ l 1
6 * * l 6
6 _ _ l 1
7 0 0 l 7
7 * * r 8

8 0 _ r 9
8 x x r 4
9 0 0 r 9
9 x x r 10
10 0 0 r 10
10 _ 0 l 11
11 0 0 l 11
11 x x l 12
12 0 0 l 12
12 _ 0 r 8
13 * _ r 13
13 _ _ r halt

LittlePeng9 (talk) 14:14, April 23, 2013 (UTC)

Divisor sum

Compute the sum of the divisors of \(n\).

LittlePeng9's answer

0 1 1 l 1
1 _ _ l 2
2 _ 1 r 3
3 _ _ l 4

4 x x l 4
4 1 x r 5
4 _ _ r 8
5 x x r 5
5 _ _ r 6
6 x x r 6
6 1 x l 7
6 _ _ l 25
7 x x l 7
7 _ _ l 4

8 x 1 r 8
8 _ _ r 9
9 x x r 9
9 1 1 l 7
9 _ _ l 10

10 x 1 l 10
10 _ y l 11
11 1 x l 12
11 x x l 11
11 _ _ l 15
12 1 1 l 12
12 _ _ l 13
13 x x l 13
13 _ x r 14
13 1 1 l 12
14 * * r 14
14 y y l 11
15 * * l 15
15 x x l 16
16 x x l 16
16 _ _ r 17
17 x 1 r 17
17 * * r 17
17 y y l 18

18 1 1 l 18
18 x 1 l 18
18 _ 1 l 19
19 1 _ l 18
19 _ _ r 20
20 * * r 20
20 y _ l c0

c0 1 1 l c0
c0 * * r c1
c1 1 x r c2
c1 _ _ r 21
c2 1 1 r c2
c2 * * r c3
c3 1 1 r c3
c3 * * l c4
c4 1 x l c5
c4 _ x r 26
c5 1 1 l c5
c5 * * l c0

21 * * r 21
21 _ _ l 22
22 x 1 l 22
22 1 1 l 22
22 _ _ l 23
23 x x l 23
23 _ _ r 24
24 x 1 r 24
24 _ _ l 4

25 x 1 l 25
25 _ y l 18

26 x x r 26
26 _ _ l 27
27 x _ l 27
27 _ _ l 28
28 1 1 l 28
28 _ _ l 29
29 _ _ r halt
29 1 1 r 30
30 _ 1 r 31
31 1 1 r 31
31 _ _ l 32
32 1 _ l 28

Note - states c0-c5 is Aarex's comparison machine, modified to handle x like blank and with modified output.

LittlePeng9 (talk) 05:17, April 5, 2013 (UTC)

Pi

Compute digits of pi in any base of your choice.

Partition function

Ignoring order, there are five distinct sums that add to 4:

  • 4
  • 3 + 1
  • 2 + 2
  • 2 + 1 + 1
  • 1 + 1 + 1 + 1

Compute the number of ways you can add positive integers to get \(n\).

LittlePeng9's answer

0 1 1 l 0
0 x 1 l 0
0 _ _ l 1
1 _ _ l 2
1 1 1 l 0
1 x 1 l 0

2 1 1 l 2
2 _ 1 r 3
3 _ _ r 4
3 1 1 r 3
4 _ _ r 4
4 1 1 r 5
5 1 1 r 5
5 _ _ r 6
6 1 1 r 5
6 _ _ l 7

7 _ _ l 7
7 1 1 l 8
8 1 1 r 9
8 _ _ l 11
9 1 _ r 10
10 _ 1 l 0

11 1 1 l 12
11 _ _ r 33
12 _ _ l 11
12 1 1 r 13
13 1 _ r 13
13 _ 1 r 14
14 1 1 r 15
14 _ _ l 21
15 _ 1 r 16
16 1 _ r 15
16 _ _ l 17
17 1 _ l 18
18 _ _ l 19
18 1 1 r 14
19 1 1 l 18

20 1 1 r 20
20 * * l 21
21 1 x l 22
21 _ _ r 30
22 1 1 l 22
22 * * l 23
23 1 1 l 23
23 * * r 24
24 1 x r 25
24 _ _ l 26
25 1 1 r 25
25 * * r 20

26 * * l 26
26 _ _ r 27
27 x 1 r 27
27 _ _ r 28
28 * 1 r 28
28 _ 1 l 29
29 1 _ l 21

30 * 1 r 30
30 _ _ r 31
31 _ _ l 0
31 1 1 r 32
32 1 1 r 32
32 _ _ l 21

33 _ _ r 34
34 1 1 r 33
34 _ _ l 35
35 _ _ l 36
36 1 _ l 35
36 _ _ l halt

LittlePeng9 (talk) 17:53, April 6, 2013 (UTC)

Expansion

Compute \(a \{\{1\}\} b\).

LittlePeng9's answer

Using my linear array notation machine.

0 1 1 l 0
0 _ | l z1
z1 _ x r z2
z2 * * r z2
z2 _ _ r z3
z3 * * r z3
z3 _ _ r z4
z4 _ 1 r z5
z5 _ _ r z6
z6 _ 1 r z7
z7 _ 1 r z8
z8 _ | l z9
z9 * * l z9
z9 x x r 0a

0a * * r 0a
0a _ _ r 1
0a | | r 0'a
0'a * * r 0'a
0'a _ _ r 1
0'a | _ l h0
1 _ _ r 1
1 1 1 r 2
2 _ _ r 3
2 | _ l 4
2 1 1 r 5
3 * _ r 3
3 | _ l 4
4 * * l 4
4 1 _ l r0
5 1 1 r 5
5 | _ l 6
5 _ _ r 9
6 1 x l 7
6 _ 1 l s1
7 * * l 7
7 | | r 8
7 x x r 8
8 1 x r s0
8 _ 1 r s3
9 1 1 r 10
9 _ _ r 9
9 y y l b0
10 1 1 r 11
10 _ _ r 9
10 | _ l 12
11 1 1 r 11
11 _ _ r 9
11 | | l 15
12 1 _ l 13
13 _ | l 14
14 * * l 14
14 | | r 0a
15 * * l 15
15 | | r c0
15 x x r c0
15 y y r c0

c0 1 x r c1
c0 _ y r c3
c0 | | r c6
c1 * * r c1
c1 | | r c2
c2 * * r c2
c2 _ x l c5
c3 * * r c3
c3 | | r c4
c4 * * r c4
c4 _ y l c5
c5 * * l c5
c5 | | l 15
c6 x 1 r c6
c6 y _ r c6
c6 _ | l 16

16 * * l 16
16 | | r 17
17 1 1 r 17
17 _ _ r 18
18 1 1 r 18
18 _ 1 l 19
18 | _ l 20
19 1 _ r 18
20 1 | l 21
21 * * l 21
21 | | l 22
22 x 1 l 22
22 y _ l 22
22 | | r 23

23 1 1 r 23
23 _ _ r 24
24 1 1 r 24
24 _ _ r 25
25 1 y r 26
26 1 1 l 27
26 _ _ r 25
27 y _ l 27
27 _ _ l 28
28 1 1 l 28
28 y y l 27
28 _ _ r 29
29 1 x r 30
30 * * r 30
30 | | r 0a

r0 _ _ l r0
r0 1 _ l r1
r0 | _ l r7
r1 * * l r1
r1 x 1 r r2
r2 1 x r r3
r2 _ x r r5
r2 | | r h0
r3 * * r r3
r3 | | r r4
r4 1 1 r r4
r4 _ _ l r0
r5 _ _ r r6
r5 1 _ r r10
r5 y _ r r13
r6 * * r r6
r6 | | r r4
r7 1 | l r8
r8 1 1 l r8
r8 _ 1 l r9
r8 x x r 32
r9 1 _ l r8
r9 _ _ l r9
r9 y _ l r14
r9 x _ r r9'
r9' _ _ l 31
r9' * * l 14
r10 _ 1 r r11
r10 1 1 r r10
r10 | 1 r r12
r11 _ _ r r11
r11 1 _ r r10
r12 _ _ l r7
r12 1 | l r1
r13 _ y r r5
r14 _ y l r9

b0 * * l b0
b0 | | r b0'
b0' 1 x r b0
b0 x 1 r b1
b1 _ _ r b7
b1 1 x r b2
b2 * * r b2
b2 y 1 r b3
b3 _ y r b4
b4 y _ r b3
b4 1 _ r b5
b5 1 1 r b5
b5 _ 1 r b4
b5 | 1 r b6
b6 _ | l b0
b7 * * r b7
b7 y 1 r 9

h0 * * l h0
h0 | 1 l h1
h1 * _ r halt

s0 * * r s0
s0 x x l 6
s1 * * l s1
s1 x x r s2
s2 1 _ r s4
s3 1 1 r s3
s3 x _ r s4
s4 * 1 r s4
s4 _ _ l s5
s5 * * l s5
s5 x 1 l s5
s5 | | r p0

p0 1 1 l p0a
p0 _ _ r p19
p0a | | r p0b
p0b 1 _ r p1
p1 1 _ r p21
p1 _ _ r p10
p1 x _ r p11
p2 * * r p2
p2 _ _ r p3
p3 1 _ r p4
p3 x _ l p8
p4 1 1 r p4
p4 _ x r p5
p4 x x r p5
p5 1 1 r p5
p5 _ 1 l p6
p6 1 1 l p6
p6 * * l p7
p7 1 1 l p7
p7 _ 1 r p3
p8 1 1 l p8
p8 x x l p8
p8 _ x l p9
p9 1 1 l p8
p9 _ _ r p10
p10 x _ r p1
p10 1 1 l p20
p11 1 1 r p11
p11 x _ r p11
p11 _ _ l p12
p12 1 1 l p12
p12 _ _ r m0
m0 1 _ r m1
m0 _ _ r m9
m1 1 1 r m1
m1 _ _ r m2
m2 1 _ r m3
m2 _ _ l m7
m3 1 1 r m3
m3 _ _ r m4
m4 1 1 r m4
m4 _ 1 l m5
m5 1 1 l m5
m5 _ _ l m6
m6 1 1 l m6
m6 _ 1 r m2
m7 1 1 l m7
m7 _ _ l m8
m8 1 1 l m8
m8 _ _ r m0
m9 1 _ r m9
m9 _ 1 r p13
p13 1 1 r p13
p13 _ _ l p14
p14 1 _ l p15
p15 1 1 l p15
p15 _ 1 l p16
p16 1 1 r p17
p16 _ _ r p13
p16 x _ r p18
p16 | | r p22
p17 1 _ l p12
p18 1 _ r halt
p19 1 _ r p19
p19 _ 1 r halt
p20 * * l p20
p20 x _ r halt
p21 * * r p2
p21 _ x r p3
p22 1 1 r p22
p22 _ _ l p23
p23 1 _ l r0

31 _ x r 32
32 * * r 32
32 | _ l r7

LittlePeng9 (talk) 09:10, April 6, 2014 (UTC)

Lychrel number test

Test whether the entered number is a Lychrel number or not. The machine should halt if the number is not Lychrel, and the machine should continue infinitely if it is.

Alternatively, develop an oracle TM that determines whether a number is Lychrel or not.

LittlePeng9's answer

; Input - number written in decimal
0 * * r 0
0 _ x l 2
0' 0 _ l 0a
0' _ _ r 3
0' x _ r p0
0a _ 0 r 0b
0b _ _ r 0c
0c * * r 0c
0c _ _ r 0d
0c x x r 0d
0d * * r 0d
0d _ 0 l 1
0' 1 _ l 1a
1a _ 1 r 1b
1b _ _ r 1c
1c * * r 1c
1c _ _ r 1d
1c x x r 1d
1d * * r 1d
1d _ 1 l 1
0' 2 _ l 2a
2a _ 2 r 2b
2b _ _ r 2c
2c * * r 2c
2c _ _ r 2d
2c x x r 2d
2d * * r 2d
2d _ 2 l 1
0' 3 _ l 3a
3a _ 3 r 3b
3b _ _ r 3c
3c * * r 3c
3c _ _ r 3d
3c x x r 3d
3d * * r 3d
3d _ 3 l 1
0' 4 _ l 4a
4a _ 4 r 4b
4b _ _ r 4c
4c * * r 4c
4c _ _ r 4d
4c x x r 4d
4d * * r 4d
4d _ 4 l 1
0' 5 _ l 5a
5a _ 5 r 5b
5b _ _ r 5c
5c * * r 5c
5c _ _ r 5d
5c x x r 5d
5d * * r 5d
5d _ 5 l 1
0' 6 _ l 6a
6a _ 6 r 6b
6b _ _ r 6c
6c * * r 6c
6c _ _ r 6d
6c x x r 6d
6d * * r 6d
6d _ 6 l 1
0' 7 _ l 7a
7a _ 7 r 7b
7b _ _ r 7c
7c * * r 7c
7c _ _ r 7d
7c x x r 7d
7d * * r 7d
7d _ 7 l 1
0' 8 _ l 8a
8a _ 8 r 8b
8b _ _ r 8c
8c * * r 8c
8c _ _ r 8d
8c x x r 8d
8d * * r 8d
8d _ 8 l 1
0' 9 _ l 9a
9a _ 9 r 9b
9b _ _ r 9c
9c * * r 9c
9c _ _ r 9d
9c x x r 9d
9d * * r 9d
9d _ 9 l 1
1 * * l 1
1 _ _ l 2
1 x x l 2
2 * * l 2
2 _ _ r 0'

3 1 0 l 4
3 2 1 l 4
3 3 2 l 4
3 4 3 l 4
3 5 4 l 4
3 6 5 l 4
3 7 6 l 4
3 8 7 l 4
3 9 8 l 4
3 0 9 r 3
3 _ _ l r0
4 * * l 4
4 _ _ l 5
5 _ _ l 6
6 1 2 r 7
6 2 3 r 7
6 3 4 r 7
6 4 5 r 7
6 5 6 r 7
6 6 7 r 7
6 7 8 r 7
6 8 9 r 7
6 9 0 l 6
6 * 1 r 7
7 * * r 7
7 _ _ r 0'

p1 * * l p1
p1 _ _ r p0
p0 _ 1 l halt
p0 0 _ r 00
00 * * r *
00 _ _ l 01
01 0 _ l p1
01 _ 1 l halt
01 * _ l h0
p0 1 _ r 10
10 * * r *
10 _ _ l 11
11 1 _ l p1
11 _ 1 l halt
11 * _ l h0
p0 2 _ r 20
20 * * r *
20 _ _ l 21
21 2 _ l p1
21 _ 1 l halt
21 * _ l h0
p0 3 _ r 30
30 * * r *
30 _ _ l 31
31 3 _ l p1
31 _ 1 l halt
31 * _ l h0
p0 4 _ r 40
40 * * r *
40 _ _ l 41
41 4 _ l p1
41 _ 1 l halt
41 * _ l h0
p0 5 _ r 50
50 * * r *
50 _ _ l 51
51 5 _ l p1
51 _ 1 l halt
51 * _ l h0
p0 6 _ r 60
60 * * r *
60 _ _ l 61
61 6 _ l p1
61 _ 1 l halt
61 * _ l h0
p0 7 _ r 70
70 * * r *
70 _ _ l 71
71 7 _ l p1
71 _ 1 l halt
71 * _ l h0
p0 8 _ r 80
80 * * r *
80 _ _ l 81
81 8 _ l p1
81 _ 1 l halt
81 * _ l h0
p0 9 _ r 90
90 * * r *
90 _ _ l 91
91 9 _ l p1
91 _ 1 l halt
91 * _ l h0

h0 * _ l h0
h0 _ _ l h1
h1 _ _ l h1
h1 * * l 2

r0 9 _ l r0
r0 _ _ l r1
r1 _ _ l r1
r1 * * l r2
r2 * * l r2
r2 _ _ r 0

Bounded version - input is made of 2 x's divided by any number of blanks, followed by 3 or more blanks and then number. Say there is n blanks. Then machine makes \(\lfloor {n \over 3} \rfloor\) reverse-and-add operations.

0 x x r 0x
0x _ _ r 0x
0x x x r 0x
0x * * r 0
0 * * r 0
0 _ x l 2
0' 0 _ l 0a
0' _ _ r 3
0' x _ r p0
0a _ 0 r 0b
0b _ _ r 0c
0c * * r 0c
0c _ _ r 0d
0c x x r 0d
0d * * r 0d
0d _ 0 l 1
0' 1 _ l 1a
1a _ 1 r 1b
1b _ _ r 1c
1c * * r 1c
1c _ _ r 1d
1c x x r 1d
1d * * r 1d
1d _ 1 l 1
0' 2 _ l 2a
2a _ 2 r 2b
2b _ _ r 2c
2c * * r 2c
2c _ _ r 2d
2c x x r 2d
2d * * r 2d
2d _ 2 l 1
0' 3 _ l 3a
3a _ 3 r 3b
3b _ _ r 3c
3c * * r 3c
3c _ _ r 3d
3c x x r 3d
3d * * r 3d
3d _ 3 l 1
0' 4 _ l 4a
4a _ 4 r 4b
4b _ _ r 4c
4c * * r 4c
4c _ _ r 4d
4c x x r 4d
4d * * r 4d
4d _ 4 l 1
0' 5 _ l 5a
5a _ 5 r 5b
5b _ _ r 5c
5c * * r 5c
5c _ _ r 5d
5c x x r 5d
5d * * r 5d
5d _ 5 l 1
0' 6 _ l 6a
6a _ 6 r 6b
6b _ _ r 6c
6c * * r 6c
6c _ _ r 6d
6c x x r 6d
6d * * r 6d
6d _ 6 l 1
0' 7 _ l 7a
7a _ 7 r 7b
7b _ _ r 7c
7c * * r 7c
7c _ _ r 7d
7c x x r 7d
7d * * r 7d
7d _ 7 l 1
0' 8 _ l 8a
8a _ 8 r 8b
8b _ _ r 8c
8c * * r 8c
8c _ _ r 8d
8c x x r 8d
8d * * r 8d
8d _ 8 l 1
0' 9 _ l 9a
9a _ 9 r 9b
9b _ _ r 9c
9c * * r 9c
9c _ _ r 9d
9c x x r 9d
9d * * r 9d
9d _ 9 l 1
1 * * l 1
1 _ _ l 2
1 x x l 2
2 * * l 2
2 _ _ r 0'

3 1 0 l 4
3 2 1 l 4
3 3 2 l 4
3 4 3 l 4
3 5 4 l 4
3 6 5 l 4
3 7 6 l 4
3 8 7 l 4
3 9 8 l 4
3 0 9 r 3
3 _ _ l r0
4 * * l 4
4 _ _ l 5
5 _ _ l 6
6 1 2 r 7
6 2 3 r 7
6 3 4 r 7
6 4 5 r 7
6 5 6 r 7
6 6 7 r 7
6 7 8 r 7
6 8 9 r 7
6 9 0 l 6
6 * 1 r 7
7 * * r 7
7 _ _ r 0'

p1 * * l p1
p1 _ _ r p0
p0 _ 1 l halt
p0 0 _ r 00
00 * * r *
00 _ _ l 01
01 0 _ l p1
01 _ 1 l halt
01 * _ l h0
p0 1 _ r 10
10 * * r *
10 _ _ l 11
11 1 _ l p1
11 _ 1 l halt
11 * _ l h0
p0 2 _ r 20
20 * * r *
20 _ _ l 21
21 2 _ l p1
21 _ 1 l halt
21 * _ l h0
p0 3 _ r 30
30 * * r *
30 _ _ l 31
31 3 _ l p1
31 _ 1 l halt
31 * _ l h0
p0 4 _ r 40
40 * * r *
40 _ _ l 41
41 4 _ l p1
41 _ 1 l halt
41 * _ l h0
p0 5 _ r 50
50 * * r *
50 _ _ l 51
51 5 _ l p1
51 _ 1 l halt
51 * _ l h0
p0 6 _ r 60
60 * * r *
60 _ _ l 61
61 6 _ l p1
61 _ 1 l halt
61 * _ l h0
p0 7 _ r 70
70 * * r *
70 _ _ l 71
71 7 _ l p1
71 _ 1 l halt
71 * _ l h0
p0 8 _ r 80
80 * * r *
80 _ _ l 81
81 8 _ l p1
81 _ 1 l halt
81 * _ l h0
p0 9 _ r 90
90 * * r *
90 _ _ l 91
91 9 _ l p1
91 _ 1 l halt
91 * _ l h0

h0 * _ l h0
h0 _ _ l h1
h1 _ _ l h1
h1 * * l 2

r0 9 _ l r0
r0 _ _ l r1
r1 _ _ l r1
r1 * * l r2
r2 * * l r2
r2 x _ l r3
r3 _ _ l r4
r4 _ _ l r5
r5 _ x r 0x

r3 x x * halt
r4 x x * halt
r5 x x * halt

Boolean expressions

Compute arbitrary expression in Boolean logic-language.

LittlePeng9's answer

Expression A is balanced iff: 1. A is either T or F 2. A=~B for balanced B or 3. A=(B) for balanced B or 4. A=(B*C) for balanced B and C (take care about parenthesis) where * represents one of binary operators - and (&), or (|), implies (>), is implied (<), xor (+), iff/xnor (-). Valid input is balanced expression with X's at both ends. Output is truth value of that expression.

0 X X r 0'
0' * * r 0'
0' ~ ~ r 1
0' X _ l 15
1 _ _ r 1
1 ( ( r 0'
1 ~ ~ r 1
1 T F l 7
1 F T l 7
0' ) _ l 2
2 * * l 2
2 ( _ l 6
2 | _ r 3
2 & _ r 8
2 > _ l 9
2 < _ r 11
2 - _ l 13
2 + _ l 14
3 _ _ r 3
3 F _ l 5
3 T T l 4
4 _ _ l 4
4 * _ l 5
5 * * l 5
5 ( _ l 6
6 * * l 6
6 X X r 0'
7 * * l 7
7 ~ _ l 6
8 _ _ r 8
8 T _ l 5
8 F F l 4
9 _ _ l 9
9 T _ l 5
9 F T r 10
10 _ _ r 10
10 * _ l 5
11 _ _ r 11
11 T _ l 5
11 F T l 12
12 _ _ l 12
12 * _ l 5
13 _ _ l 13
13 T _ l 5
13 F ~ l 5
14 _ _ l 14
14 F _ l 5
14 T ~ l 5
15 * * l 15
15 X _ r halt

Calculator

Simulate a pocket calculator. It should at least support 0123456789=+-×. Order of operations and floating-point arithmetic are optional.

LittlePeng9's answer

I made this one in like one hour. It can compute a+b=, a-b= or axb=, where a and b are written in decimal.

0 * * r 0
0 + + l 1
0 - - l 1
0 x x l 1

1 1 0 r 2
1 2 1 r 2
1 3 2 r 2
1 4 3 r 2
1 5 4 r 2
1 6 5 r 2
1 7 6 r 2
1 8 7 r 2
1 9 8 r 2
1 0 9 l 1
1 _ _ r 4
2 * * r 2
2 _ 1 l 3
3 * * l 3
3 + + l 1
3 - - l 1
3 x x l 1
4 * _ r 4
4 + _ r +0
4 - _ r -0
4 x _ r x0

+0 * * r +0
+0 = = l +1
+1 1 0 r +2
+1 2 1 r +2
+1 3 2 r +2
+1 4 3 r +2
+1 5 4 r +2
+1 6 5 r +2
+1 7 6 r +2
+1 8 7 r +2
+1 9 8 r +2
+1 0 9 l +1
+1 _ _ r 5
+2 * * r +2
+2 _ 1 l +3
+3 * * l +3
+3 = = l +1

-0 * * r -0
-0 = = l -1
-1 1 0 r -2
-1 2 1 r -2
-1 3 2 r -2
-1 4 3 r -2
-1 5 4 r -2
-1 6 5 r -2
-1 7 6 r -2
-1 8 7 r -2
-1 9 8 r -2
-1 0 9 l -1
-1 _ _ r 5
-2 * * r -2
-2 _ _ l -3
-3 1 _ l -4
-3 = _ l -5
-4 * * l -4
-4 = = l -1
-5 * _ l -5
-5 _ 0 r halt

x0 * * r x0
x0 _ x l +3

5 * _ r 5
5 = = r 6
6 * * r 6
6 _ _ l 7
6 x _ l 10
7 1 _ l 8
7 = _ l 7'
7' _ 0 r halt
7' * * r halt
8 * * l 8
8 = = l 9
9 _ 1 r 6
9 0 1 r 6
9 1 2 r 6
9 2 3 r 6
9 3 4 r 6
9 4 5 r 6
9 5 6 r 6
9 6 7 r 6
9 7 8 r 6
9 8 9 r 6
9 9 0 l 9

10 1 1 l 10
10 = _ r m0

m0 1 _ r m1
m0 _ _ r m9
m1 1 1 r m1
m1 _ _ r m2
m2 1 _ r m3
m2 _ _ l m7
m3 1 1 r m3
m3 _ _ r m4
m4 1 1 r m4
m4 _ 1 l m5
m5 1 1 l m5
m5 _ _ l m6
m6 1 1 l m6
m6 _ 1 r m2
m7 1 1 l m7
m7 _ _ l m8
m8 1 1 l m8
m8 _ _ r m0
m9 1 _ r m9
m9 _ = r 6

LittlePeng9 (talk) 20:39, May 1, 2013 (UTC)

Although it gives 10-11=0, that is very impressive! FB100Ztalkcontribs 19:20, May 3, 2013 (UTC)
I used standard arithmetic definition of subtraction - \(a\dot{-}b:=\begin{cases}a-b&\text{if }a>b\\0&\text{otherwise} \end{cases}\)

Second version, capable of multiple operations. Left associative.

0 * * r 0
0 + + l 1
0 - - l 1
0 x x l 1
0 _ _ l halt

1 1 0 r 2
1 2 1 r 2
1 3 2 r 2
1 4 3 r 2
1 5 4 r 2
1 6 5 r 2
1 7 6 r 2
1 8 7 r 2
1 9 8 r 2
1 0 9 l 1
1 _ _ r 4
2 * * r 2
2 _ 1 l 3
3 * * l 3
3 _ _ r 3'
3' * * r 3'
3' + + l 1
3' - - l 1
3' x x l 1
4 * _ r 4
4 + _ r +0
4 - _ r -0
4 x _ r x0

+0 * * r +0
+0 = = l +1
+0 + + l +1
+0 - - l +1
+0 x x l +1
+1 1 0 r +2
+1 2 1 r +2
+1 3 2 r +2
+1 4 3 r +2
+1 5 4 r +2
+1 6 5 r +2
+1 7 6 r +2
+1 8 7 r +2
+1 9 8 r +2
+1 0 9 l +1
+1 _ _ r 5
+2 * * r +2
+2 _ 1 l +3
+3 * * l +3
+3 _ _ r +4
+4 * * r +4
+4 = = l +1
+4 + + l +1
+4 - - l +1
+4 x x l +1

-0 * * r -0
-0 = = l -1
-0 + + l -1
-0 - - l -1
-0 x x l -1
-1 1 0 r -2
-1 2 1 r -2
-1 3 2 r -2
-1 4 3 r -2
-1 5 4 r -2
-1 6 5 r -2
-1 7 6 r -2
-1 8 7 r -2
-1 9 8 r -2
-1 0 9 l -1
-1 _ _ r 5
-2 * * r -2
-2 _ _ l -3
-3 1 _ l -4
-3 = _ l -5
-4 * * l -4
-4 _ _ r -6
-5 * _ l -5
-5 _ 0 r halt
-6 * * r -6
-6 = = l -1
-6 + + l -1
-6 - - l -1
-6 x x l -1

x0 * * r x0
x0 _ x l +3

5 * * r 5
5 + + r 5'
5 - - r 5'
5 x x r 5'
5 9 _ r 5
5' * * r 5'
5' = = r 6
5 = = r 6
6 * * r 6
6 _ _ l 7
6 x _ l 10
7 1 _ l 8
7 = = l 7a
7a * * l 7a
7a _ _ r halt
7a + + l 7b
7a - - l 7b
7a x x l 7b
7b * * l 7b
7b _ _ r 0
8 * * l 8
8 _ _ r 8'
8' * * r 8'
8' = = l 9
8' + + l 9
8' - - l 9
8' x x l 9
9 _ 1 r 5
9 0 1 r 5
9 1 2 r 5
9 2 3 r 5
9 3 4 r 5
9 4 5 r 5
9 5 6 r 5
9 6 7 r 5
9 7 8 r 5
9 8 9 r 5
9 9 0 l 9

10 * * l 10
10 _ = r 11
11 * * r 11
11 = _ r m0

m0 1 _ r m1
m0 _ _ r m9
m1 1 1 r m1
m1 _ _ r m2
m2 1 _ r m3
m2 _ _ l m7
m3 1 1 r m3
m3 _ _ r m4
m4 1 1 r m4
m4 _ 1 l m5
m5 1 1 l m5
m5 _ _ l m6
m6 1 1 l m6
m6 _ 1 r m2
m7 1 1 l m7
m7 _ _ l m8
m8 1 1 l m8
m8 _ _ r m0
m9 1 _ r m9
m9 _ = r 12

12 1 1 r 12
12 _ _ l 13
13 1 _ l 14
13 = _ l 19
14 * * l 14
14 = = l 15
15 * * l 15
15 = = r 16
16 * * r 16
16 _ _ l 17
16 + + l 17
16 - - l 17
16 x x l 17
17 = 1 l 17'
17 0 1 r 18
17 1 2 r 18
17 2 3 r 18
17 3 4 r 18
17 4 5 r 18
17 5 6 r 18
17 6 7 r 18
17 7 8 r 18
17 8 9 r 18
17 9 0 l 17
17' _ = r 18
18 * * r 18
18 = = r 12

19 _ _ l 19
19 * * r 20
20 _ = l 21
21 * * l 21
21 = _ r 0

LittlePeng9 (talk) 16:04, May 10, 2013 (UTC)

Arbitrary root

Compute m-ractic (m-th power) root of given n.

LittlePeng9's answer

Input is simply strings of n and m 1's separated by blank. Output is equal to \(\lfloor \sqrt[m]{n} \rfloor\)

0 1 1 r 0
0 _ x r s0
0a 1 _ r 1
1 1 _ r 20
1 _ _ r 10
1 x _ r 11
2 * * r 2
2 _ _ r 3
3 1 _ r 4
3 x _ l 8
4 1 1 r 4
4 _ x r 5
4 x x r 5
5 1 1 r 5
5 _ 1 l 6
6 1 1 l 6
6 * * l 7
7 1 1 l 7
7 _ 1 r 3
8 1 1 l 8
8 x x l 8
8 _ x l 9
9 1 1 l 8
9 _ _ r 10
10 x _ r 1
10 1 1 l 15
11 1 1 r 11
11 x _ r 11
11 _ _ l 12
12 1 1 l 12
12 _ _ r m0
m0 1 _ r m1
m0 _ _ r m9
m1 1 1 r m1
m1 _ _ r m2
m2 1 _ r m3
m2 _ _ l m7
m3 1 1 r m3
m3 _ _ r m4
m4 1 1 r m4
m4 _ 1 l m5
m5 1 1 l m5
m5 _ _ l m6
m6 1 1 l m6
m6 _ 1 r m2
m7 1 1 l m7
m7 _ _ l m8
m8 1 1 l m8
m8 _ _ r m0
m9 1 _ r m9
m9 _ 1 r 13
13 1 1 r 13
13 _ _ l 14
14 1 _ l 15
15 1 1 l 15
15 _ 1 l 16
16 1 1 r 17
16 _ _ r 13
16 x _ r 18
17 1 _ l 12
18 1 1 r 18
18 _ _ l 19
19 1 _ l c1
20 * * r 2
20 _ x r 3
s0 1 1 r s0
s0 _ _ r s1
s1 _ 1 r s2
s1 1 1 l s3
s2 _ 1 l s3
s3 * * l s3
s3 x _ r d0
d0 1 x r d1
d0 _ _ r d5
d1 1 1 r d1
d1 _ _ r d2
d2 1 1 r d2
d2 _ _ r d3
d3 _ 1 l d4
d3 1 1 r d3
d4 * * l d4
d4 x x r d0
d5 1 x r d6
d5 _ x r 0a
d6 1 1 r d6
d6 _ _ r d7
d7 1 1 r d7
d7 _ _ r d8
d8 _ 1 l d9
d8 1 1 r d8
d9 * * l d9
d9 x x r d5
c0 1 * r c0
c0 x x r c5
c0 _ _ l c1
c1 1 _ l c2
c1 _ 1 l f0
c2 * * l c2
c2 _ * l c3
c3 1 * l c3
c3 _ 1 r c4
c3 x x l c2
c4 1 _ r c5
c4 _ _ l h0
c5 1 * r c5
c5 x x r c5
c5 _ _ r c0
f0 x 1 l f0
f0 _ _ l f1
f1 x 1 l f0
f1 1 1 l f1
f1 _ 1 l f2
f2 1 1 l f2
f2 _ _ r f3
f3 1 _ r 0
h0 1 _ l h0
h0 _ _ r h1
h1 _ _ r h1
h1 x _ r h2
h2 x _ r h2
h2 _ _ r h3
h3 x 1 r h3
h3 _ _ r h4
h4 1 _ r h4
h4 _ _ l h5
h5 * * l h5
h5 1 _ l halt

Now machine works as supposed. I forgot to put working one here.

LittlePeng9 (talk) 20:10, May 6, 2013 (UTC)

Cellular automaton

Create a TM that simulates an elementary cellular automaton of your choice. Elementary cellular automata operate on infinite tapes; how to deal with this is up to you. Note that if you simulate Rule 110, you'll have a universal TM.

LittlePeng9's answer

C++ generating any of 256 Wolfram rules:

#include<conio.h>
#include<iostream>
#include<fstream>
using namespace std;

ofstream outFile("Wolfram.txt");

int main(){
	int x=0;
	cin>>x;
	if(x>255){
		cout<<"Input must be smaller than 256";
		getch();
	}
	else{
		outFile<<"0 0 "<<x%2<<" r 0"<<endl;x=x/2;
		outFile<<"0 1 "<<x%2<<" r 1"<<endl;x=x/2;
		outFile<<"1 * "<<x%2<<" r 2"<<endl;x=x/2;
		outFile<<"1 1 "<<x%2<<" r 3"<<endl;x=x/2;
		outFile<<"2 * "<<x%2<<" r 0"<<endl;x=x/2;
		outFile<<"2 1 "<<x%2<<" r 1"<<endl;x=x/2;
		outFile<<"3 * "<<x%2<<" r 2"<<endl;x=x/2;
		outFile<<"3 1 "<<x%2<<" r 3"<<endl<<endl;
		outFile<<"0 _ _ l 4"<<endl;
		outFile<<"4 * * l 4"<<endl;
		outFile<<"4 _ _ r 0";
	}
	return 0;
}

Not very compact, but works. Input is automaton's number in Wolfram's numbering. Input for machine is simply string of 0's. It works for finite inputs only, though. LittlePeng9 (talk) 07:40, June 8, 2013 (UTC)

Float root

Compute \(\sqrt{n}\) to infinite precision. That is, the Turing machine should continue adding digits of precision as it runs infinitely.

String subsequence

Determine whether the one sequence of strings is a subsequence of other (arbitrary number of types of symbols).

LittlePeng9's answer

Example input: to check if 132 is subsequence of 21233132 replace number 1 in every string with '1', every 2 with '11', every 3 with '111' and leave blanks between them. Input is first string followed by 2 blanks and second string. Output is character under halted machine head (1 if it is subsequence, blank otherwise)

; Example input: 132 and 21233132 -> 1 111 11  11 1 11 111 111 1 111 11
0 1 x r 1
0 _ _ r 10
1 _ _ r 2
1 * * r 1
2 1 1 r 1
2 _ _ r 3
3 _ _ r 3
3 x x r 4
4 x x r 4
3 1 x l 6
4 1 x l 5
4 _ _ r 4a
4a _ _ l halt
4a 1 1 l 4b
4b _ _ l 7
5 x x l 5
5 _ _ l 6
6 * * l 6
6 x x r 0
7 x _ l 7
7 _ _ l 8
8 * * l 8
8 x 1 l 9
9 x 1 l 9
9 _ _ r 0
9 1 _ r 0
10 * * r 10
10 x _ r 11
11 x _ r 11
11 1 _ r 12
11 _ _ l 13
12 1 _ r 12
12 _ _ r 12a
12a 1 1 l 8
12a _ _ l halt
13 * * l 13
13 x x l 14
14 x x l 14
14 _ _ r 15
14 1 _ r 15
15 x _ r 15
15 _ 1 r 16
16 1 x r 1
16 _ _ l halt

LittlePeng9 (talk) 10:49, April 6, 2013 (UTC)

Friedman string

Detect whether the given string is Friedman string (they are described in the block subsequence theorem article).

Extended Up-arrow Notation

Compute Extended Up-arrow Notation.

2-dimensional Array Notation

Compute Extended Array Notation up to {n,m(2)2}.

Goucher's T(n) function

Compute Adam P. Goucher's T(n) function.

LittlePeng9's answer

Input is n+1 1's, output is T(n) exactly

0 1 1 l 1
1 _ ! l 3
2 * _ l 2
2 x _ l 2'
2' x 1 l 2'
2' * * r halt
3 _ x r 4
4 * * r 4
4 ! ! r 5
4 _ _ r 5
5 1 1 r 5
5 _ _ r 6
6 1 1 r 5
6 _ _ l 7
7 _ _ l 7
7 1 _ l 8
8 _ _ l 9
8 1 1 l 8'
8 ! 1 l 2
8' ! _ r 2
8' 1 1 l 11
8' _ _ l 12
9 * * l 9
9 x x l 10
10 * * l 10
10 _ 1 r 4
11 1 1 l 11
11 _ _ l 12
11 ! | l 19
12 * * l 12
12 1 1 l 13
13 1 1 l 13
13 * * r c1
c0 1 1 l c0
c0 * * r c1
c0 y y l c5
c1 1 x r c2
c1 * | l 27
c2 1 1 r c2
c2 y y r c2
c2 * * r c3
c3 1 1 r c3
c3 y y r c2
c3 * * l c4
c4 1 x l c5
c4 * _ r 14
c5 1 1 l c5
c5 y y l c5
c5 * * l c0
14 x x r 14
14 _ _ l 15
15 x 1 l 15
15 y y l 15
15 _ _ l 16
16 x y l 16
16 1 y l 16
16 y y l 15
16 _ _ l 13
16 ! ! r 17
17 y 1 r 17
17 _ _ r 17
17 1 1 l 18
18 * * l 18
18 ! | l 19
19 x x l 19
19 * * r 20
20 x y r 21
20 _ _ r 23
21 x x r 21
21 _ _ r 22
21 | | r d0
22 * * r 22
22 | | r d0
d0 1 x r d1
d0 _ y r d8
d0 | | r d11
d1 1 1 r d1
d1 _ _ r d2
d1 | | r d6
d2 1 1 r d1
d2 _ 1 l d3
d3 _ | r d4
d4 1 1 r d4
d4 _ | l d5
d5 * * l d5
d5 x x r d0
d5 y y r d0
d6 * * r d6
d6 | 1 r d7
d7 _ | l d5
d8 * * r d8
d8 | | r d9
d9 * * r d9
d9 | _ r d10
d10 _ | l d5
d11 * * r d11
d11 | _ l d12
d12 * * l d12
d12 | | l d13
d13 x 1 l d13
d13 y _ l d13
d13 | _ l d14
d14 * * l d14
d14 y y r 20
23 * * r 23
23 | _ l 24
24 * * l 24
24 y y l 25
25 y y l 25
25 _ x r 26
25 1 x l 25'
25' 1 1 l 25'
25' _ 1 r 26
26 * x r 26
26 1 1 r 26
26 _ ! r 5
27 x x l 27
27 _ _ r 28
28 x 1 r 28
28 | | r 29
29 y 1 r 29
29 _ _ r 29
29 x 1 r 30
30 x 1 r 30
30 _ _ l 31
31 * * l 31
31 ! _ l 19

LittlePeng9 (talk) 20:41, May 11, 2013 (UTC)

Warp Notation

Compute Warp Notation.

Fast-growing hierarchy

Simulate FGH for some large recursive ordinal.

f111...111(111...111) (with m and n ones respectively corresponds to \(f_m(n)\)). So, the limit ordinal for this is \(\omega\).

0 * * r 0
0 _ * l 3
0 ( * r 1
1 f * r 0
1 1 * l 1
1 2 _ r 4
1 ( * l 2
2 1 * l 2
2 f _ r 0a
3 ) _ l 3
3 1 * l 3
3 2 _ l 3
3 _ * l halt
4 * * r 4
4 _ | l 5
5 * * l 5
5 _ * r 7f
;A-block
0a * * r 0a
0a _ | r 1a
1a _ f l 2a
2a * * l 2a
2a _ f r 3a
3a 1 _ r 4a
3a ( _ r 6a
3a ) _ r 8a
4a * * r 4a
4a _ 1 l 5a
5a * * l 5a
5a _ 1 r 3a
6a * * r 6a
6a _ ( l 7a
7a * * l 7a
7a _ ( r 3a
8a * * r 8a
8a _ ) l 9a
9a * * l 9a
9a ) _ l 10a
9a _ * l 11a
10a _ * l 10a
10a 1 _ l 10a
10a ( _ l 10a
10a ) _ l 10a
10a f _ r 0b
11a * _ l 11a
11a f 2 r 0b
;B-block
0b * * r 0b
0b | * r 1b
1b f _ r 2b
2b 1 f r 3b
2b ( 1 r 0g
3b 1 * r 3b
3b ( * r 4b
4b 1 _ l 5b
4b ) _ l 9b
5b * * l 5b
5b | * l 6b
6b 1 * l 6b
6b _ 1 r 7b
7b * * r 7b
7b ( * r 8b
8b 1 * r 8b
8b _ 1 r 4b
9b 1 _ l 9b
9b ( * l 0c
;C-block
0c * * l 0c
0c | * l 1c
1c 1 _ l 2c
2c 2 * l 3c
2c * * l 2c
2c f * l 3c
3c 1 * l 3c
3c _ 1 r 4c
3c f * l 3c
3c ( * l 3c
3c 2 1 r 4c
4c * * r 4c
4c _ * r 5c
5c _ * r 5c
5c 1 * r 6c
5c f * r 5c
5c | * l 7c
6c 1 * r 6c
6c _ 1 l 1c
6c ( * r 6c
6c | * l 7c
7c 1 * l 7c
7c _ * r 0d
;D-block
0d | * l 0e
0d 1 _ r 1d
1d * * r 1d
1d f _ r 2d
2d * * r 2d
2d _ f l 3d
3d * * l 3d
3d _ f r 4d
4d 1 _ r 5d
4d ( _ r 7d
5d * * r 5d
5d _ 1 l 6d
6d * * l 6d
6d _ 1 r 4d
7d * * r 7d
7d _ ( l 8d
8d * * l 8d
8d _ ( l 9d
9d * * l 9d
9d | * l 10d
10d 1 * l 10d
10d _ * r 0d
;E-block
0e 2 * l 1e
0e * * l 0e
0e f * l 1e
1e 1 * l 1e
1e _ | r 2e
1e ( * l 1e
1e f * l 1e
2e 1 _ r 3e
2e f * l 7e
2e 2 * l 7e
3e * * r 3e
3e | * r 4e
4e _ * r 5e
5e * * r 5e
5e _ 1 l 6e
6e * * l 6e
6e _ * l 0d
7e | _ l 7e
7e _ * r 7e
7e f * r 8e
7e 1 _ r 7e
7e 2 * r 8e
8e * * r 8e
8e | _ r 9e
9e _ * r 10e
10e * * r 10e
10e _ * l 0f
;F-block
0f _ * r 2f
0f * * l 0f
0f ( [ r 1f
1f * * r 1f
1f _ ) l 0f
2f * * r 2f
2f [ ( r 2f
2f _ * l 3f
3f ) * r 4f
4f _ ) r 5f
5f _ | l 6f
6f * * l 6f
6f _ * r 7f
7f _ * r 7f
7f 1 _ l 10f
7f f _ l 8f
7f ( _ l 12f
7f ) _ l 14f
7f | _ l 16f
8f _ * l 8f
8f 2 * r 9f
8f ( * r 9f
9f _ f r 7f
10f _ * l 10f
10f * * r 11f
11f _ 1 r 7f
12f _ * l 12f
12f * * r 13f
13f _ ( r 7f
14f _ * l 14f
14f * * r 15f
15f _ ) r 7f
16f _ * l 16f
16f ) * l 17f
17f * * l 17f
17f _ * r 0
;G-block
0g 1 * r 0g
0g ) * r 1g
1g _ | l 2g
2g * * l 2g
2g _ * l 3g
3g | _ r 7f

Nested Up-arrow Notation

Compute Nested Up-arrow Notation.

Conway's Game of Life

Simulate behavior of Game of Life two-dimensional cellular automaton.

Busy Beaver Function Lite™

Compute \(\Sigma(n)\) for a specific, small value of \(n\), e.g. \(\Sigma(2)\).

SKI calculus

Simulate the beta reduction for expressions in SKI calculus.

Kirby-Paris hydras

Made Turing machine that able to reduce any arbitrary Kirby-Paris hydra to its root.

LittlePeng9's answer

Input is ( followed by blank followed by hydra. Intermediate hydras are unbalanced, but output is exactly as if it wasn't.

0 * * r 0
0 _ _ r 1
1 * * r 1
1 _ _ l 2
2 * _ l 2
2 ( _ r 5

3 _ _ r 4
4 ( ( r 4'
4 ) _ r 27
4' * * r 4'
4' _ _ r 2

5 _ ) r 6
6 * * r 6
6 _ _ r 7
7 ) ) r 7
7 _ ) l 8
8 ) ) l 8
8 _ _ l 9
9 * * l 9
9 _ _ l 10
10 ) _ r 5
10 ( _ r 11
10 _ ( r 3
11 _ ( r 12
12 * * r 12
12 _ _ r 13
13 ) ) r 13
13 _ _ l 14
14 ) _ l 15
15 ) ) l 8
15 _ _ l 16

16 * * l 16
16 _ _ l 17
17 * * l 17
17 _ _ l 18
18 ( ( l 18
18 ) ( r 19
18 _ ( r 19
19 ( ) r 20
19 _ _ r 22
20 ( ( r 20
20 _ _ r 21
21 * * r 21
21 _ _ r c0

c0 ( _ l (1
c0 ) _ l )1
c0 _ ( r c3
(1 _ ( r (2
(2 _ _ r (3
(3 * * r (3
(3 _ _ r (4
(4 * * r (4
(4 _ ( l c1
)1 _ ) r )2
)2 _ _ r )3
)3 * * r )3
)3 _ _ r )4
)4 * * r )4
)4 _ ) l c1
c1 * * l c1
c1 _ _ l c2
c2 * * l c2
c2 _ _ r c0
c3 ( ( r c3
c3 ) ) l c4
c4 ( ) r c5
c5 ) ) r c5
c5 ( ( l c6
c5 _ _ l c7
c6 ) ( r c3
c7 ) _ l 16

22 * * r 22
22 _ _ r 23
23 * * r 23
23 _ _ l 24
24 ) _ l 25
25 ) ) l 25
25 ( ) l 26
26 ) ( l 25
26 ( ( l 26
26 _ ( r 1

27 _ _ r 27
27 ) _ l halt

LittlePeng9 (talk) 20:45, May 11, 2013 (UTC)

Cascading-E notation

Compute an arbitrary expression in E^.

Quine

Construct a machine which, when run on empty tape, writes down its own program in format of your choice.

Graham's problem

Compute the exact solution of Graham's problem that currently bounded by \(13 \leq N \leq 2 \uparrow\uparrow 2 \uparrow\uparrow 2 \uparrow\uparrow 9\).

n(k) function

Compute n(k) for given n.

Goodstein function

Compute G(n) for given n.

Extended Cascading-E Notation

Compute Extended Cascading-E Notation.

TREE function

Compute TREE(n) for given n.

Homeomorpic embedding

Determine whether one graph is homeomorphically embeddable to the second one.

SCG function

Compute SCG(n) for given n.

Bird's U Function

Compute U(n).

Buchholz hydras

Made Turing machine that able to reduce any arbitrary Buchholz hydra to its root.

Bird's array notation

Compute arbitrary expression in Bird's array notation.

Hyperfactorial array notation

Compute Hyperfactorial array notation.

Dollar function

Compute Dollar Function.

Wythagoras's answer

current version works for a and [0]. Here

Wythagoras (talk) 19:05, August 1, 2013 (UTC)

Loader's D(n) function

Compute D(n) for given n.

Web browser

Simulate a web browser using a TM.

LittlePeng9's answer

Click LittlePeng9 (talk) 18:57, August 5, 2014 (UTC)

Polyominoes function

Given n, compute how many distinct polyominoes with size n exist.

Ramsey number

Compute nth Ramsey number.

LittlePeng9's answer

0 * * r 0
0 _ _ l 19
0 1 X l 15
15 _ | l 16
15 * * l 18
16 _ | l 17
17 _ | l 18
18 * * l 18
18 _ 0 r 0
19 X 1 l 19
19 | | l 19
19 0 0 r 20
20 | _ r 20
20 1 0 l 14
14 _ _ l 1
1 _ | r 2
2 _ _ r 3
3 * * r 3
3 _ _ r 11
3 0 X r 4
3 1 B r 9
4 * * r 4
4 _ _ r 5
5 * * r 5
5 _ 1 r 6
6 _ 0 l 7
7 * * l 7
7 _ _ l 8
8 * * l 8
8 _ _ r 3
9 * * r 9
9 _ _ r 10
10 * * r 10
10 _ 1 l 7
11 * * r 11
11 _ _ l 12
12 0 _ l 13
12 1 _ l 8
13 1 1 l 13
13 _ | r C0

T0 | | r T1
T0 * * l T23
T1 * * r T1
T1 | | r T2
T2 X X r T2
T2 1 X l T3
T2 0 0 r T6
T2 _ _ r T7
T3 * * l T3
T3 | | l T4
T4 * * l T4
T4 | | r T5
T5 * * r T5
T5 _ | r T1
T6 * * r T6
T6 _ _ r T7
T7 X X r T7
T7 1 X l T8
T7 0 0 l T12
T7 * * l T12
T8 * * l T8
T8 | | l T9
T9 * * l T9
T9 | | r T10
T10 * * r T10
T10 X x r T11
T10 R r r T11
T10 B b r T11
T11 * * r T11
T11 | | r T6
T12 * * l T12
T12 x x r T32
T12 r r r TR0
T12 b b r TB0
TR0 * * r TR0
TR0 | | r TR1
TR1 * * r TR1
TR1 _ _ r TR2
TR2 * * r TR2
TR2 _ R l T13
TR2 R _ l T13
TR2 B _ l 32
TB0 * * r TB0
TB0 | | r TB1
TB1 * * r TB1
TB1 _ _ r TB2
TB2 * * r TB2
TB2 _ B l T13
TB2 B _ l T13
TB2 R _ l 32
T13 * * l T13
T13 | | r T14
T14 X | r T15
T14 0 | r T17
T14 _ _ r T21
T15 * * r T15
T15 _ _ r T16
T16 * * r T16
T16 X 1 l T19
T16 0 1 l T20
T17 * * r T17
T17 _ _ r T18
T18 * * r T18
T18 X x l T19
T18 0 x l T20
T19 * * l T19
T19 | 1 r T14
T20 * * l T20
T20 | x r T14
T21 1 1 r T21
T21 x x r T21
T21 * * l T22
T21 _ _ l T24
T22 * * l T22
T22 x 0 l T22
T22 | | l T23
T23 * * l T23
T23 x X l T23
T23 r R l T23
T23 b B l T23
T23 | _ l T0
T24 * * l T24
T24 | | r T25
T25 1 1 r T25
T25 x 1 r T26
T25 _ _ l T28
T26 * * r T26
T26 _ _ r T27
T27 * * r T27
T27 _ _ l T22
T28 1 x l T28
T28 | | r T29
T29 x 1 r T30
T30 x x r T30
T30 _ _ r T31
T31 1 1 r T31
T31 x 1 r T27
T31 _ _ l 36
T32 * * r T32
T32 | | r T33
T33 * * r T33
T33 _ _ r T34
T34 * * r T34
T34 _ _ l T13

C0 * * r C0
C0 1 X l C1
C0 0 R l C11
C0 _ _ l C18
C1 * * l C1
C1 | | l C2
C2 * * l C2
C2 | _ r C3
C3 _ | r C4
C4 * * r C4
C4 | | r C5
C5 * * r C5
C5 X x l C6
C5 1 B l C6
C5 0 b l C6'
C5 R r l C6'
C5 _ _ l C10
C6 * * l C6
C6 | | l C7
C7 * * l C7
C7 | | r C8
C8 X | l C8X
C8 R | l C8R
C8 B | l C8B
C8X | X r C9
C8R | r r C9
C8B | b r C9
C9 * * r C9
C9 | | r C4
C6' * * l C6'
C6' | | l C7'
C7' * * l C7'
C7' | | r C8'
C8' X | l C8X'
C8' R | l C8R'
C8' B | l C8B'
C8X' | X r C9
C8R' | R r C9
C8B' | B r C9
C10 b 0 l C10
C10 B 1 l C10
C10 r R l C10
C10 x X l C10
C10 | | r C0

C11 * * l C11
C11 | | l C12
C12 * * l C12
C12 | _ r C13
C13 _ _ r C14
C14 * * r C14
C14 _ _ l C15
C14 | | l C15
C15 X | l C15X
C15 R | l C15R
C15 B | l C15B
C15X X X l C15X
C15X R X l C15R
C15X B X l C15B
C15R X R l C15X
C15R R R l C15R
C15R B R l C15B
C15B X B l C15X
C15B R B l C15R
C15B B B l C15B
C15X _ X r C16
C15R _ R r C16
C15B _ B r C16
C16 * * r C16
C16 | | r C17
C17 * * r C17
C17 | | r C0

C18 R 0 l C18
C18 X 1 l C18
C18 | | l C19
C19 * * l C19
C19 r R l CR0
C19 b B l CB0
CR0 * * l CR0
CR0 r R l CR0
CR0 b B l C20
CR0 _ _ l CR1
CR1 * * l CR0
CR1 r R l CR0
CR1 b B l C20
CR1 _ _ r 21
CB0 * * l CB0
CB0 r R l C20
CB0 b B l CB0
CB0 _ _ l CB1
CB1 * * l CB0
CB1 r R l C20
CB1 b B l CB0
CB1 _ _ r 21
C20 * * l C20
C20 r R l C20
C20 b B l C20
C20 _ _ l C21
C21 * * l C20
C21 r R l C20
C21 b B l C20
C21 _ _ r C22
C22 _ | r C22_
C22_ _ _ r C22_
C22_ X _ r C22X
C22_ R _ r C22R
C22_ B _ r C22B
C22X _ X r C22_
C22X X X r C22X
C22X R X r C22R
C22X B X r C22B
C22R _ R r C22_
C22R X R r C22X
C22R R R r C22R
C22R B R r C22B
C22B _ B r C22_
C22B X B r C22X
C22B R B r C22R
C22B B B r C22B
C22X | X r C23
C23 * * r C23
C23 _ _ l C24 
C24 1 1 l C24
C24 0 0 l C25
C25 0 0 l C25
C25 1 0 r C26
C24 | | l 48
C25 | | l 48
C26 0 1 r C27
C27 0 0 r C27
C27 _ _ l C29
C27 1 0 l C28
C28 0 0 l C28
C28 1 1 r C26
C29 * * l C29
C29 | | r C0

21 _ | r 22_
22_ _ _ r 22_
22_ X _ r 22X
22_ R _ r 22R
22_ B _ r 22B
22X _ X r 22_
22X X X r 22X
22X R X r 22R
22X B X r 22B
22R _ R r 22_
22R X R r 22X
22R R R r 22R
22R B R r 22B
22B _ B r 22_
22B X B r 22X
22B R B r 22R
22B B B r 22B
22X | X l 23
23 * * l 23
23 | | r 24
24 * * r 24
24 | _ l 63
24 R B r 24
24 B R r 25
25 * * r 25
25 | | r 26
26 * * r 26
26 _ x l 27
27 * * l 27
27 1 X r 28
27 0 X r 28
27 | | r 29
28 * * r 28
28 _ X l 27
29 X 1 r 30
30 X 0 r 30
30 x _ r 29
30 _ _ l 31
31 * * l 31
31 | | r T2

32 * _ l 32
32 _ _ l 33
33 * 1 l 33
33 | | l 34
34 * * l 34
34 x X l 34
34 b B l 34
34 r R l 34
34 | _ l 35
35 * * l 34
35 x X l 34
35 b B l 34
35 r R l 34
35 | | r 24

36 * _ l 36
36 _ _ l 37
37 * 0 l 37
37 | | l 38
38 * * l 38
38 x X l 38
38 b B l 38
38 r R l 38
38 | _ l 39
39 * * l 38
39 x X l 38
39 b B l 38
39 r R l 38
39 | | l 40
40 _ x l 41
41 1 1 l 41
41 0 1 r 42
41 _ _ r 46
42 * * r 42
42 | | r 43
43 * * r 43
43 | | r 44
44 0 1 l 45
44 1 1 r 44
45 * * l 45
45 x x l 41
46 1 0 r 46
46 x _ r 46
46 | | r 47
47 * * r 47
47 | | r C0

48 * * l 48
48 | | r 49
49 _ _ r 50
50 X X r 50
50 * B r 50
50 _ B r 51
50 1 R l 54
51 * | r 51B
51_ * _ r 51B
51B X B r 51X
51B R B r 51B
51B B B r 51B
51B _ B r 51_
51X X X r 51X
51X R X r 51B
51X B X r 51B
51X _ X r 51_
51X * X l 52
52 * * l 52
52 | _ r 50
53 B R r 54
53 X R r 54
53 1 1 l 53
53 R R l 53
53 _ _ r 55
54 * * r 54
54 _ R l 53
55 R B r 55
55 1 0 l 56
55 0 _ r 55
55 _ | l 58
56 B R l 57
57 B X r 55
58 * * l 58
58 B 0 r 59
58 _ _ r 60
59 * * r 59
59 _ 0 l 58
60 0 B r 60
60 | | l 61
61 B X l 62
62 * * l 62
62 | | l 40

63 * _ l 63
63 0 _ l 64
64 0 _ l 64
64 _ _ r 65
65 _ _ r 65
65 * 1 r 66
66 * 1 r 66
66 _ _ l halt

LittlePeng9 (talk) 12:20, May 4, 2015 (UTC)

Busy beaver function (for oracle Turing machines)

Compute \(\Sigma(n)\) for given n.

Greagol

Compute Greagol.

Community content is available under CC-BY-SA unless otherwise noted.