10,667 Pages

!Ikosarakt1 inspired me to get back to TM programming.

These machines are designed to work on this simulator.

News: the simulator we are using got redesigned - few news things were added. First: now we can share Turing machines by adding links! What more, we can share them along with ready input, and we can even share them at some point of the computation!

Secondly, now we can pause computation: if we write ! after a line of code, then machine will pause when this transition is executed. However, it crashes simulator when running at full speed. It works now, if anyone is interested.

Thirdly, halt states now have customizable names - any state name of which starts with "halt" will count as halting state, so we can have something like "haltAccept", "halt-reject".

## Pólya conjecture test

Challenge - prove this machine halts

## Restricted Knuth up-arrow notation

Example input - x^^^x^^^^xx It corresponds to $$2\uparrow 2 \uparrow \uparrow 3$$

Question - how many states we need to add in order to compute Ackermann function? I found 7 is enough

### Two color restricted Knuth up-arrow notation

Same rules as above - strings of x's and ^'s replace with strings of 1's with blanks inbetween. Output isn't decreased by 1 in here

Example input - 1 111 1 1111 11 It corresponds to $$2\uparrow 2 \uparrow \uparrow 3$$

## Two color Collatz conjecture tester

Works for one given number only

### Binary version

This machine isn't my construction, I've seen it in one cellular automaton (this one. I also made improved version of this automaton, if anyone is interested) and recreated it as simple TM. Input is binary number written backwards.

## Root calculator

### Square root calculator

#### 3-color version

For every natural number it returns $$\lfloor \sqrt{n} \rfloor$$

#### 2-color version

Works same way as previous machine, expect for marking. It uses single blank space as end of marked part. Suprisingly, time complexity haven't increased much.

Challenge: I didn't bother to make it work for all integers. Change it. It should be possible with 5 new states

### Arbitrary root calculator

Edit: machine fixed. It works now for every b>0

## Binary logarithm calculator

It works only for powers of 2. Even now it is very inefficient. Calculates $$log_2(1024)$$ in 1082294 steps.

### Improved version

This version computes $$\lceil log_2(n)\rceil$$ for any n and has fewer states at the same time. It's also faster, computes $$log_2(1024)$$ in 703277 steps.

## Prime factorization

I posted it in Turing golf, here is commented version I used same principle as in Pólya conjecture checker

## Divisor sum calculator

Again, just commented version as in Turing golf

## Multiplication

I found out trying to improve Ikosarakt's ideas is kind of fun. Machine doesn't handle a<2 and/or b=0.

### Improved version

I swear! I found this one by accident! I tried to make separated copies of input, but something went wrong

### List multiplication

Guess which Turing golf challenge I'm going to solve with help of this machine. Input format: (a1) (a2)...(an)  (b1) (b2)...(bn) where (m) means string of m 1's. Output: (a1*b1) (a2*b2)...(an*bn)

### Taking number to arbitrary power

Given input (a) (b) calculates b^a

Edit: machine fixed for a<3

## Factorial

We can reduce machine by 2 states, if we allow it to don't handle number 1 (and no else). In second transition we have to replace x0 with 1, so states x will never be used

## How to compute n(3)

This is my try to compute n(3). Here are needed elements and ready machine

### String subsequence determiner

I improved Ikosarakt's design, and I think I improved it much. It works for any number of characters, for n characters it uses 2+2*n states (reduced 3 states, because now I can use different halting state names), and has simplier input: write sequence we search for and sequence being search space. Note: this machine uses lemma I found - consider sequences $$a_1a_2...a_n$$ and $$b_1b_2...b_m$$. Search algorithm is as this: find smallest $$k_1$$ such that $$a_1=b_{k_1}$$. Now find smallest $$k_2>k_1$$ such that $$a_2=b_{k_2}$$ etc. We call sequence $$b_{k_1}b_{k_2}...b_{k_n}$$ (if it exists) a minimal subsequence. If minimal subsequence exists, it is isomorphic to a, so a is subsequence of b. Lemma states inverse relation holds: if a is subsequence of b, there exists minimal subsequence.

Challenge: prove this lemma

### Dividing string into elements to compare

For every n it gives, from given input, substring (n,2n). This is designed for 3 characters: a,b,c. Every character has a replacement - x,y,z, respectively. To add new character, for every transition containing a or x replace them with appropriate character or replacement.

### Property * determiner

As defined by Friedman, set of strings has property * iff for no two strings this set one is subsequence of another.

### Friedman string recognizer

String $$x_1x_2x_3...$$ is called Friedman string iff set $$\lbrace x_1x_2,x_2x_3x_4,x_3x_4x_5x_6,...$$ has property * (look above)

### n(3) calculator

Putting everything together was easier than I thought. If someone counts states and colors, we'll have bound $$n(3)<\Sigma(s,c)$$, although this bound is crushed by machine below (less states, less colors, much larger output).

### How to modify machine to compute n(k)

Here I'll add character p with replacement q and second replacement r. You can add this exact ruleset and modify counter to compute n(4) easily. To add one character we need 3 new states.

Adding character consists of 2 steps: we need additional ruleset to handle new state:

r2 p p l r3

d0 p q r dp0
dp0 * * r dp0
dp0 _ _ r dp1
dp1 * * r dp1
dp1 _ p l d2

d3 q p r d0

5 p _ r 6p
6p * * r 6p
6p 1 p l 8
6p _ _ r 7p
7p _ 1 l 12
7p 1 p l 8
7p * * r 6p

8 q q l 9
9 q q r 10
9' q _ l 21
11 p q r 6p
13 p q r 14
17 q p l 17
18 q p l 18
19 q p l 18

c0 p q r c1p
c1a p r r c2a
c1b p r r c2a
c1c p r r c2a
c1p * * r c1p
c1p _ 1 r c2p
c1p x m r c2p
c1p y n r c2p
c1p z o r c2p
c1p p r r c2p ; You have to add similar transition for every character you add
c2p * * r c2p
c2p p q l c3
c2p _ _ r c4a
c3 q q r c0
c4 p r l c4
c4 q r l c4
c5 q p l c5
c7 r p l c7
c7 q p l c7


Explanation of comment - if you already added, say, t with 2nd replacement u, we also need c1p t u r c2p.

Secondly, we need to introduce new character. We must modify ternary counter like that:

i0 a b l i1
i0 b c l i1
i0 c d l i1
i0 d e l i1
...
i0 p a r i0


It must cycle through all characters you want to use. Order is irrelevant.

## Modified Goucher's T(n)

This is essentially same function as T(n)  function by Adam Goucher. However, in my machine, c is increased also when we delete trailing 0's.

This function is almost certainly at growth level of $$f_{\varepsilon_0}(n)$$. If it is, then, as far as I know, it is first machine which is halting for every input such that it's halting isn't provable in Peano Arithmetic

## Kirby-Paris hydra game

This time we can construct function which certainly does grow at level of $$f_{\varepsilon_0}(n)$$ (previous machine hasn't been proven to do that, although it seems sure).

This machine isn't computing actual function, it only collapses hydra, output must be of form ))...) A, where ))...) is 1 or more right parentheses and A is any tree in parenthesis form without outermost pair (i.e. root)

### 3-color version

#### Heavily improved version!

I noticed one thing - previous machine at the beginning deletes rightmost )'s and later reconstructs them. So even if at the beginning they were unbalanced, they'd balance by themselves. So they are theoretically unnecessary. This version has lost 15 states thanks to this!

Now input must have ('s at the beginning instead of )'s, and it doesn't need rightmost )'s (e.g. ( ((())) is equivalent to ( ((( ) Using just 2 states this can be converted to function comparable with $$f_{\varepsilon_0}(n)$$!

#### Reduced number of states!

Thanks to comment by Wythagoras on this blog post I was able to reduce number of states to 38. There is no state 4' now, state 14 was replaced with state 5, (1 with c3, (2 with c4, 24 with c4, )1 with c6, )2 with c7, and I did some renaming to keep numbering consistent. I'm leaving above machine for historical purposes and comparison.

#### Reduced number of states II

Reduced again by two states by Wythagoras! Note that this machine actually computes Hydra(n)+1.

## Buchholz's hydra

Yes, I started work on Buchholz's hydra game. For now I'm not planning implementing whole game, rather just parts for machines or partial results. Never mind, I did it anyway :D

Important - every part of hydra not inside parenthesis (i.e. connected to root) must be inside () pair. For example, [[]] is invalid, so is (()[])[(())]

If I'm able to extend one of above machines to cut () heads while preserving [] pairs we'll be able to reach Bachmann-Howard ordinal!

Now it should work well.

Input format: multiplier represented by string of x's followed by space and hydra

### (0,1)-labelled hydra game

I did it! I made hydra game on hydras labelled with 0's and 1's! If strength of these hydras is indeed Bachmann-Howard ordinal, I just made Turing machine undecidable within Kripke-Platek set theory!

Input format: multiplier represented by string of x's followed by space and hydra

### Finite Buchholz hydra - cutting >0 head

Differs a bit from original definition - top node becomes u instead of 0

Input format - consider standard representation of hydra using brackets with labels, e.g. 0( 3( 3) 0) where n( n) pair means node labelled with n. Each such pair we replace with n+1 left parentheses and n+1 right parentheses, e.g. above would be ( (((( )))) ). Now place any number of x's to the left as a multiplier.

### Finite Buchholz hydra game

At last my machine is done! Input format is as above. If you find any error in this, please comment it together with input.

Oh, and I forgot - multiplier of n x's actually behaves like n+1. Technical reasons.

141 states (I think) and 7 symbols - and we reached limits of $$\Pi_1^1$$-$$\text{CA}_0$$!

#### How to translate this machine into long-halting Busy Beaver

Take some 2-state 7-color machine which leaves large number of consecutive symbols (like this candidate ). Use third and fourth state to replace whole string with ('s. Now use, for example, this machine:

0 ( _ r 1
0 _ _ l halt
1 ( ( r 1
1 _ _ r 2
2 ) ) r 2
2 _ ) l 3
3 ) ) l 3
3 _ _ l 4
4 ( ( l 4
4 _ ( r 0


To make it into 2 enclosing wide parentheses. Use similar machine to make long string of x's on the left. With about 5 more states we add ( ) pair to make hydra working. So about 19 new states are sufficient to make HUGE number! This gives BB(160,7)>>most of defined computable numbers.

### Transfinite Buchholz hydra!

Just 17 states more! I hope you enjoy limits of $$\Pi_1^1-\text{CA}+\text{BI}$$! You know label 0 is represented as ( ), label 1 as (( )) etc. Label $$\omega$$ is )( )). If you find any issues please comment them below.

While trying to find mistakes in code I thought "Halting times on this machine are unimaginably large, I can't know if machine properly halts." So I added some transitions and now, if we place [ to the left of multiplier, it will never increase, thus greatly reducing halting time. It still works for very long time, though.

## Linear array notation

This machine computes version of linear arrays where {a,b}=a^b. If replace it with Bowers' original rule {a,b}=a+b, we'd save around 35 states. But I decided to go harder way.

Input format: x|A| where A is array in form of strings of 1's divided by blanks, e.g. x|111 111 111| calculates tritri

## Unrestricted Knuth's up-arrow notation

Same as restricted one, expect it doesn't have 2-in-base limitation and strings have right length (we don't decrease by 1). Again, one ^ is addition, ^^ is multiplication. Proper hyper operators require two arrows more

### Graham's number

Okay, this machine consists of 3 parts: Short setup, long setup and compute

#### Short setup

First, we need to write some setup by-hand. Namely, we need 161_111^111| with head on left end. This is made by 20-state machine, using 2^m machine by Deedlit. 1' means state 1 in next machine.

#### Long setup

This machine translates above into (111^111|)63111^^^^^^11 with head on right end end. Remember that above machine moves to state 1 in this machine!

This is achieved by 20-state machine 1' means state 1 in next machine.

#### Compute

Now this is core of machine. Shortly, it computes rightmost number and after computing it computes 3^^^...^^3 with that many arrows+2 (because of way my machine works). It repeats 63 times. This 40-state machine does all the work. Accidentaly, state numbers form nice round numbers. After summing we get 80 states. Number of colors is 5, so Turing golf score is: $$80+(5+2)^2-16=80+49-16=113<1000$$, so it still applies for competition! Within new scoring system my machine has exactly 2000 points, but, as Deedlit said, not that anyone scores their TMs anyway :P

## Goldbach conjecture

This machine halts iff Goldbach conjecture is false. If this is a case, we have pretty long lasting machine in here. But for now, as we don't know for sure if this conjecture is true or false, we can't know if this machine halts. (I know Goldbach conjecture is widely believed to be true, i.e. machine won't halt, but we aren't sure)

### Ternary Goldbach conjecture

This is similar statement to above - every odd number >7 can be represented as sum of 3 odd primes. Again, machine halts iff conjecture is false.

## Computing pi (WIP)

I'm going to use Wallis' product for computing pi. This series is slowly converging, multiplying elements up to 1000 gives 2 digits of precision.

### Numerator

Given input 2n, machine makes list of numbers 2n, 2n-2, 2n-4..., 4, 2, copies it and uses my list multiplication to do the job. Then we multiply by 2, because Wallis' formula computes half of pi, and we want whole pi.

### Denominator

Given input 2n, machine makes list of numbers 2n, 2n-2, 2n-4..., 4, 2, copies it and uses my list multiplication to do the job. From every product we subtract 1 and multiply everything together.

### Division

Given input of form (a) (b) where (n) means string of n 1's machine outputs integer part written in binary, binary dot and binary expansion of fraction

### Complete machine

Input is a bit complicated - yy...yxxx1xxx11...1 with number of y's same as number of 1's and even. Machine is very inefficient. Given 4 y's and 4 1's it takes 70000 steps before starting division. But then output is $${45\over 128}\approx 2.844...\neq \pi$$. To get better results we need literally millions of y's. Very slow convergence. At least division is pretty efficient

## Odd perfect numbers

This machine runs until it finds odd perfect number (so possibly forever). It can start on blank tape, so is potential Busy Beaver. You can check that it works by starting with input of 8 1's and waiting until it finds 28 (less than half a million steps).

## Riesel numbers

This machine halts iff input number n isn't Riesel number, i.e. for some number k number $$n\cdot 2^k-1$$ is prime. We can make this machine look through all 55 smaller Riesel number candidates such that machine halts iff none of them are Riesel, and 509203 is truly smallest one.

## Sierpiński numbers

This machine halts iff input number n isn't Sierpiński number, i.e. for some number k number $$n\cdot 2^k+1$$ is prime. We can make this machine look through 6 smaller Sierpiński number candidates such that machine halts iff none of them are Sierpiński, and 78557 is truly smallest one.

## Unary calculator

Ikosarakt constructed unary calculator which can be seen here, but it had unhandled expections, like 11-1+1=. Here is my machine, heavily using state recycling, e.g. state 8 is used for all operations, and state 2 is used for multiplication and subtraction. It solves everything left to right and allows operations: +, -, x

## Legendre's conjecture

It states that for every integer n there is prime p such that $$n^2<p<(n+1)^2$$. This machine simply searches every interval for prime number and succeds. This is my 5th TM which is equivalent to some unsolved problem. I want to show that is so called RE-hard problem, i.e. every recursively enumerable problem is translateable to some halting instance. If we could solve halting problem, so we could every RE problem.

## Catalan–Mersenne number conjecture

It says that numbers of form $$M_{M_{..._{M_2}}}$$ are all primes up to a certain limit. I can prove that otherwise all such numbers are prime. This is what machine checks.

## Fermat prime search

If there for some n>4 $$2^{2^n}$$ is prime, machine halts. But this machine is very uneffective and checks all powers of 2.

## Regular paperfolding sequence

This machine isn't my idea, I've seen it on some Turing machine simulator some time ago. I just recreated it.

Input is $$2^n-1$$ 1's for any $$n>0$$, output is exactly that many characters of dragon curve sequence

## Direct simulation of binary TMs

This is first truly universal Turing machine made by me. This machine has stationary "program box", which is simply program of binary TM we want to simulate. On the left and right side of the box is input. Currently scanned cell is on right of box. Detailed construction of box below. Example: |X1>R 1>L 1<L 0>L 1<<< 1>L 1R 0<<<R| simulates 4-state busy beaver.

### Program construction

For every state we have 2 transitions: transition for symbol 0 and for symbol 1. Say we are in state a and we want to transit to state b, where a and b  are natural numbers. First character of transition is symbol we want to write. Then, if a>b, we write a-b >'s. If a<b, we write b-a <'s. If a=b we add nothing. Then, we write either R or L, depending on direction machine moves. It doesn't support "don't move". For example, if we have transition from state 2 to state 7 writing 1 and moving left, we have 1>>>>>L. The program box is constructed as follows: first is |, then blank, then transition for state 0 symbol 0, blank, transition for state 0 symbol 1. blank, state 1 symbol 0, blank, state 1 symbol 1 etc. and end with |. If we want machine to halt, we give transition suffiscently many >'s or <'s to run out of states. Finally, we put X instead of blank before state n, symbol 0 where n is starting state. You can now add input for constructed machine to the left or to the right using 0's and 1's. Complicated to explain, easier to do.

### Universality proof

We know that any Turing machine can be simulated by 2-color Turing machine. Such reduction is bounded by exponential function. Now that binary machine can be simulated by above machine, with reduction bounded by polynominal. So this reduction is do-able in recursive time, thus can't be universal. Machine universally simulating machines with non-universal reduction is universal, Q.E.D.

## SKI combinator calculus (WIP)

Right now it works with all combinators, but can only execute I and K combinators. I'm not planning to implement $$\Omega$$, but you can try yourself :P

It works with fully parenthesised expressions like ((SS)(KS)) as well as partially, like SS(KS) Small modification - machine now supports O as instant halt command. Because oracle is impossible to do, when we hit a point where O must be used machine stops, and you can by hand execute next step.

## Vector reduction

Let us have {a,b,...} as a vector to reduce as here. Then input is |(a)|(b)... where (n) is string of n 1's (n=0 is empty string). I think I got this one more compact than Ixfd's Python program. I'm not sure if it works correctly, any testing appreciated.

## Laver tables

My goal here is to create a machine which will find the value of $$q(n)$$, which potentially is an extremely fast growing function, but we don't really know.

### Construction

The basic idea is that I have found somewhere, and this is confirmed in Laver's paper, that as long as a table satisfies $$x*(y*1)=(x*y)*(x*1)$$ and has size $$2^k$$, then it's a Laver table. This can also be used to construct the table recursively after one realizes that $$x*y>x$$ as long as $$x\neq 2^k$$ (note: Laver in his paper uses 0 where we nowadays usually put $$2^k$$).

The input now has the form: (this is for k=2, you can extrapolate from this how it'd look for arbitrary k)

|000 000 000 000 |000 000 000 000 |000 000 000 000 |000 000 000 000 |


FINALLY DONE

This machine is ridiculously fast, it has computed 8x8 Laver table in less than 420000 steps. I don't know if I have ever been this proud of a machine I have created :P

### Setup

On input consisting of $$2^k$$ ones, the machine will construct input required to build Laver table of size $$2^k$$.

### Period of the first row

Given input like in the construction machine, except that 0's can be replaced with 1's, the output is p |'s, where p is the period of the first row.

### $$q(n)$$

So I've decided not to implement specifically a machine computing $$p(n)$$ and went straight ahead to a machine computing $$q(n)$$. If you want to see the machine really working, try to run it on the old version of the simulator, which is faster.

I think I will convert this machine into CA and try to run it on input 3, or maybe even 4.

If anyone manages to run this machine on input 5 or higher from the start until the halt, I'll buy them a cookie.

Okay, so I have tried to run the machine on CA in order to confirm that $$q(4)=6$$, but when I've noticed machine went past that Laver table, I was totally scared that I have messed something up hard. I later quickly ran the machine and indeed got $$q(3)=5$$, so I thought either something is wrong, or something else is wrong. Turns out the article on the Wiki is wrong, which I have no idea how that happened, as the article stated something different from what's on OEIS.

If anyone is interested, the machine took about 150 billion steps to compute 6th Laver table (this one runs quite fast, it took about 15 minutes to get), and I think less than 1 billion to compute 5th one.

## Direct simulation of 2-counter machines

This is a project similar to my direct simulation of binary TMs.

### 6-color version

Here it is, my second (finished) computationally universal Turing machine! Look below for how-to-use guide.

### 4-color version (WIP)

Coming... probably some day. Possibly never. But I hope for the best :P

### Program construction

There are 5 possible inctructions: increment + counter, increment - counter, decrement + counter or conditional jump, decrement - counter or conditional jump, unconditional jump. Programs for 2CM can be written in the following manner:

INC+
INC-
DEC+ N
DEC- N
GOTO N


Where INC means "increment respective counter", DEC* N means "decrement respective counter, and jump to N-th instruction if 0", and GOTO N means "jump to N-th instruction". In my machine the coding is following:

INC+     +
INC-     ++
DEC+     -+
DEC-     --
GOTO     +-


We also have to code N into last 3 instructions - this is done by adding +'s or -'s to the right of this instructions, depending on if we want to go to instruction earlier or later in program. This is fairly straightforward, e.g. +-+++ will jump to instruction 3 to the right, ----- will conditionally jump to instruction 3 to the left. Halt instruction "caps" the whole program, and it doesn't have to be coded in any way.

Input for my machine starts with a single |, which marks current instruction. Later we write instructions separated by single blanks. Then we write two blanks, and everything to the right codes counters in the following way:

1st, 3rd, 5th, 7th... cell of that part of tape codes + counter. All other cells code - counter. Number of +'s and -'s represent numbers stored in counters, e.g. the following stores 5 in + and 3 in - counter:

+-+-+-+ +


(NOTE: if - counter is not empty, but + is, then there will be 3 blanks between instructions and first -)

Example input:

|-++++ ++ +--- --++++ + + +----  + + +


This simply doubles number in + counter, which is 3 in this example.

### Universality proof

First, we can encode any binary TM by a 3CM (original argument due to Minsky, iirc): in the first counter we store left side of the tape interpreted as binary number, in second we store right side. Third counter is used as scratch, to make all necessary operations on first two counters. I'm not going to go into great detail here.

Second, we can encode 3CM by a 2CM: first we code numbers apperent in 3 counters into one number using Godelization: if counters store numbers $$A,B,C$$ then we code it using $$2^A3^B5^C$$. Second counter is then, again, used as a scratch.

Last, but not least, my machine can simulate any 2CM, which ends universality proof.

## Cyclic tag systems

I'm on universality hype now, so maybe I'll go and finish SKI machine later?

### Program construction

(I assume you all know how cyclic tag systems work)

For every production tag system makes we have to add 0 at the end (I made it so that we can handle empty productions). Now input for the machine is as following: modified productions are separated by single blanks and we add |'s at the beginning and the end. After | on the left we put tag system data. Also, I allowed myself to implement halt command: if machine uses production ending with 1 (not 0, like all modified productions) Example:

|0100 0 1 10100|1101001


## Neary's binary tag systems

Yesterday I found particularily simple computationally universal model - certain restricted model of binary tag systems, which have only two characters (in paper denoted b,c and in my machine 0,1) and thus two prosuction rules. However, production rule for 0 is trivial (it just appends another 0 at the end), so it could be easily hard-coded into machine's program. Look below for how to create input for machine.

### Program construction

We have 3 variables for these tag systems - deletiong number $$\beta$$, production rule $$u$$ for when 1 is read, and dataword $$w$$. Input is simply $$u$$ with 0 added at the end followed by blank, followed by $$\beta$$ 1's, followed by blank and dataword. Example:

11011100 11111 1


Here $$u=1101110$$, $$w=1$$, $$\beta=5$$

### Universality proof

Someone has discovered a truly marvelous proof of this, which this blog post is too short to contain. So I'm gonna link it: boop

## Boolean satisfiability

The question about acceptation of this machine is NP-complete.

### Input construction

I will work on this example, coding $$(x_1\lor x_2\lor\neg x_3)\land(\neg x_1\lor x_2\lor\neg x_3\lor x_4)\land(x_3\lor\neg x_4)\land(x_3\lor x_4)$$:

|| FFFF|T T F 0 |F T F T |0 0 T F |0 0 T T ||


First, there are 4 variables in whole formula, so we start with || FFFF|. Only number of F's varies here. After that we have to code clauses. In the first clause, first variable appears without negation, so we represent it with T. Same for 2nd variable. 3rd variable appears negated, so F represents it. 4th variable doesn't appear, so we put 0 there. By enclosing it in |'s and putting spaces where they are needed, we get proper encoding of first clause: |T T F 0 |. We repeat same for all other clauses. We end last clause with double, instead of single, |. Result is as above. Machine tests all assignments possible and halts with FTTF at the beginning, which indeed satisfies this formula.

### OddMaxSAT

This is a variation of satfiability, and it's following question: given boolean formula, does lexicographically last satisfying assignment have least significant bit equal to 1? This problem is PNP-complete. Input construction is as above, except we start with string of T's, not F's. Example:

|| TTTT|T T F 0 |F T F T |F F 0 0 |0 0 T T ||


### Tautology problem

I've literally changed like 5 transitions in SAT machine to get tautology problem solver. Tautology problem asks if, given a formula in DNF (not in CNF like above machines) is it true for every choice of variables? This problem is co-NP complete. Input just like for machines above.

## Subset sum problem

The problem is: given a multiset (i.e. set in which elements can repeat) and a number N decide if there is some subset of this multiset such that sum of its elements is exactly N. This is another NP-complete problem. Machine below halts iff such subset exists.

### Input construction

We simply write N, blank, and then all elements of the multiset separated by blanks. At the beginning and end we put |. Example:

|11111111 1111 111 11 1111|


It checks if some subset of {4,3,2,4} sums up to 8. The output is

|00000000x1111 111 11x1111|


With x's to the left of two 4's, which means these two fours give the sum of 8.

## EXPTIME-complete problem

The following problem is EXPTIME-complete: given a Turing machine and number $$N$$ (written in binary), will the machine halt in at most $$N+1$$ steps? The following machine implements it: The input is exactly as here, expect right after first | we put binary expansion of $$N$$, written backwards in binary, like here: |111111 X1>R 1>L 1<L 0>L 1<<< 1>L 1R 0<<<R| It checks if 4-state Busy Beaver halts in at most 64 steps (which it doesn't).

## Prime number generator

Quite simple machine - writes down, one by one, all prime numbers. Writes all primes below 30 in about 135000 steps.

## st-connectivity

Also known as STCON or graph reachability. It's a decision problem asking, given directed graph $$G$$ and verticies $$s,t\in G$$, can we reach $$t$$ from $$s$$ by moving on edges of $$G$$? This problem is $$NL$$-complete (nondeterministic logarithmic space).

### Input construction

Suppose we have graph with $$n$$ vertices numbered $$1,...,n$$. Machine will tell us if there is path from $$1$$ to $$n$$.

We will write $$n$$ blocks, each composed of $$n$$ bits (i.e. 0 or 1). $$l$$th bit of $$k$$th block is 1 iff in our graph there is edge from $$k$$ to $$l$$. Example:

000110 001000 010001 110100 001010 000000


In this case, path exists, so machine halts. If there were no path, machine would lack transitions.

## Partition problem

Yet another NP-complete problem. Like in subset sum, we have a list/multiset of numbers, and we have to decide if we can partition the list into two parts with equal sums. (fun fact, I have just now found an error in the machine which I fixed by removing one state)

Input is exactly as in subset sum problem. In output we have some numbers marked with x, and some left alone. This is our partition.

Actually, neither this or subset sum machine doesn't truly solve NP-complete problem. For that, numbers would have to be written in binary.

## Graph 3-colorability

I am really surprised by how small this machine turned out to be. This is my second machine which solves truly NP-complete problem (cf. last paragraph under machine above). Input and halting conditions as in st-connectivity machine. This machine also returns what the coloring is.

Also note that this machine might not work for directed graphs, even though input construction allows these.

## Dominating set problem

Turns out that working with adjacency matrices is quite annoying, but not that difficult. Dominating set of a graph is a subset of set of its vertices such that every vertex is either in dominating set or one of its neighbours is. Dominating set problem is question: given number $$k$$, is there a dominating set of size $$\leq k$$? It uses the fact that if there is dominating set of size $$l\leq k$$, then there is one of size exactly $$k$$ (it can be proved in one or two sentences).

Btw, dominating set problem is NP-complete.

### Input consturction

To make machine small I've used following input format: first we write block of $$k$$ ones and $$n-k$$ zeroes, where $$n$$ is size of the graph. It's immediately followed by a |, blank, and then an adjacency matrix of the graph (i.e. the graph coded like in other graph machines). Example input for Petersen graph and $$k=3$$:

1110000000| 0111000000 1000101000 1000000011 1000010100 0100010001 0001100010 0100000110 0001001001 0010011000 0010100100


It halts in less than 100000 steps with affirmative result. By changing $$k$$ to $$2$$ you can find that Petersen graph has no dominating set of size 2 in 190000 steps. I'm quite surprised by speed of this machine.

## Web browser

Before you start thinking it's a joke, I can assure you this is how a real web browser might work! (based upon Google Chrome). As an input, give it any web address. Or search query. Or anything else.

## EXPSPACE-complete problem

Minor modifications to EXPTIME-complete machine results in machine solving EXPSPACE-complete problem - given binary expansion of $$N$$, does machine's work ever exceed $$N+1$$ cells? Machine also is disallowed to move to the left of its starting position. Input exactly the same as for EXPTIME machine.

## Positive 1-in-3SAT

So here is how it goes: in normal SAT, we have clauses like $$x\lor\neg y\lor\neg z$$, and for a clause to be true we need at least one out of three literals in it to be true. For 1-in-3SAT we have clauses like $$R(x,\neg y,\neg z)$$, and for $$R$$ to be true we need exactly one of three literals to be true. Furthermore, in positive 1-in-3SAT $$\neg$$ is disallowed, i.e. no negated variables. Under these restrictions, satisfiability is still NP-complete. Compared to normal SAT machine, I've cut this machine to 3 tape symbols, so input is different. First we write as many zeroes as there are variables. Then we put a single space and we start coding clauses. Clauses are strings of zeroes and ones, with each bit separated by blank. $$n$$th bit is 1 if $$n$$th variable is in clause, 0 otherwise. For example, $$R(x_1,x_2,x_3)\land R(x_2,x_3,x_5)\land R(x_1,x_4,x_5)$$ is coded as

00000 1 1 1 0 0  0 1 1 0 1  1 0 0 1 1


## Thue-Morse sequence

So SJ224 created his machine writing down Thue-Morse sequence. I decided to create my own. I have used one of equivalent definitions of this sequence (guess which one). This way the machine writes first $$O$$ bits in $$O(n\log n)$$ steps (I think).

### Modified version with less states

Less states, but has kind of a work station to the left of proper output.

## Binary logarithm of decimal number

Another machine which SJ224 created and I recreated. Mine has few states more, but I believe it computes logarithm of n digit number in $$O(\log^2 n)$$ steps.

NOTE: Due to my laziness the machine must be started up in state 5.

NOTE': Input is in decimal, output is in unary.

## Second attempt at computing pi

So I have decided to make another attempt at computing pi, in hope to create a faster machine achieving the desired effect. I have decided to give Leibniz formula a try. Whether it turns out well or not depends on if I can make a nice rational arithmetic operations.

So apparently I was able to complete this machine in less than two hours.

The input is just a string of 2n+1 ones, and after some time machine starts writing down binary expansion of $$\frac{4}{1}-\frac{4}{3}+\frac{4}{5}-\frac{4}{7}+...\pm\frac{4}{2n+1}\approx\pi$$, which is precisely Leibniz approximation. This is _extremely_ slowly converging (first 4 terms give value below 3) so I do not recommend this machine for practical uses.

### $$\ln 2$$

I have made the machine so that it's simple to change it so that it gives you approximation of $$\ln 2=\frac{1}{1}-\frac{1}{2}+\frac{1}{3}-\frac{1}{4}+...$$. For this you just have to change the following transition:

q3 _ _ r q0  ->  q3 _ _ r d0


and provide as the input an even number of ones as the input.

## Ramsey numbers

<Deedlit> Hey Wojowu, if you want an interesting TM challenge
<Wojowu> I'm all ears
<Deedlit> how about one that computes Ramsey numbers?
<Wojowu> Uh, that wouldn't be easy
<Deedlit> no it wouldn't
<Deedlit> too hard?
<Wojowu> I might give it a try


I'm giving it a try.

### Testing a coloring

The way I'm using to encode graphs is by writing down adjacency matrix with entries being either X (which is reserved for edge from a vertex to itself), R (meaning edge from n to m is red), B (same with blue). But now, we need to make sure that for every n, m edge from n to m and from m to n has the same color. This is what this machine is doing.

Input format: With adjacency matrices as described above, the input consists of a |, a space, adjaceny matrix, a | and then we have 100...0 twice, with numbers of zeroes being (number of vertices in a graph)-1. An example with 4 vertices is provided in the link above.

### Testing for clique

This machine checks if a graph, as coded above, has a singly colored clique of size c. For that, we give it input as above, but instead of double 100...0 it will have single 11...100...0 with c 1's and (number of vertices in a graph)-1 0's. Machine has to be started up on the first of these 1's.

### Setup

Input: n 1's. Output: Tape ready for checking graphs of size n in order to seek for R(n,n).

Awkward state numbering because I had to make machine do something on the beginning.

### Finished machine!

As it turns out, yesterday I was only 3 states away from completing the machine. Now, after few days of quite intensive work, the Ramsey number machine is here!

Now I am going to make this into CA and try to verify that R(3,3)=6. Wish me luck. I have tried, but after few hundred million steps I have done quick maths from which it followed that complete verification would take few trillion steps to complete, which is unreasonable number given that my computer runs the simulation at only 2 million steps per second. However I was able to look at how "endgame" would look like if the machine was to be run until the end, and from that I can confirm that it works as expected.

So yeah, Ramsey numbers! :D

## Steinhaus-Moser notation

ayy, back to Turing golf! For $$n_0$$ in $$n_1$$-gon in $$n_2$$-gon in... in $$n_k$$-gon write $$n_k$$ 1's, blank,..., $$n_2$$ 1's, blank, $$n_1$$ 1's, blank, $$n_0$$ 1's.

## Polynomial evaluation

The machine finds the value of the polynomial with positive integer coefficients and positive integer input. For that it uses Horner's method.

## Pi, take #3

So this time I am just going to approximate the area of quarter of a circle by counting the number of lattice points in first quadrant satisfying $$x^2+y^2\leq n$$ for some fixed $$n$$ (see Gauss circle problem)

### Fast squaring

I want this machine to work in quite realistic time lengths, so efficient method of squaring will be desired. It uses identity $$n^2=\sum_{i=0}^{n-1} 2i+1$$, which everyone should either know or prove as a homework.

### Counting lattice points within a circle (incomplete)

The way this machine counts lattice points within a circle of radius $$\sqrt{r}$$ (I have yet to decide if boundary points will be counted) is that it counts number if integer solutions to $$x^2+y^2<r$$ (might change to $$\leq$$) such that $$0\leq x,0<y,x+y<r$$ (last condition provides no problems if $$r>2$$, quadruples it and adds 1.

## Riemann hypothesis (WIP)

Recently, this paper has been published, which contains a description of a 2-color, 5372-state Turing machine which halts iff Riemann hypothesis is false (see section 5 for details). I decided to give this a try myself. At first I wanted to use the same equivalent statement of RH as given in the paper, but then I figured out that using Mertens function might give us a better results. In particular, I have emailed Montgomery with a question whether they know of explicit version of a conditional bound he and Maier establish, namely that under RH we have $$M(x)=O(\sqrt{x}\operatorname{exp}(C(\log x)^{39/61}))$$. Until I get a reply there is no hope in finishing the machine, but I am still constructing parts of it.

### [http://morphett.info/turing/turing.html?ce782860a87ccebb04a233713c4f057f $$\mu(n)$$

3-color, 37-state machine computing the value of $$\mu(n)$$. The input is supposed to be n 1's with the head starting on the rightmost one, and depending on the value of $$\mu(n)$$ the machine will halt into state halt0, halt+1 or halt-1.

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