FANDOM


In this blog post I'll post programs for infinite time Turing machines.

Preliminaries

Machines I'll post here are going to have only one tape. These machines don't have full power of infinite-time computability.[1]

Programs are going to be written in style similar to that used in this simulator. Because ITTM's investigated by Hamkins et al. are only one way infinite, every input will have left end marker #, and every program will have this mandatory transition:

* # * r *

Which follows convention that, if machine tries to move left of leftmost cell, it just doesn't move. No machine can have any other transition involving #. Also, moving right from this character doesn't count as a step. If I write "empty input" I will mean "only # on input tape".

In every program let L denote limit state. When machine enters limit stage, it enters L state and moves to left end marker (and instantly moves right). There is no other transition rule which allows entering L state. In my convention, L state doesn't count towards state count, just like halt state doesn't, because it's mandatory for this type of machines.

I'll make a convention on pairing function: \(\langle a,b\rangle=2^a\cdot(2b+1)-1\) (one may easily verify this is a one-to-one \(\mathbb{N}^2\rightarrow\mathbb{N}\)). This will be used to code ordinals.

Convention on accepting/rejecting input - if machine halts via transition rule, it accepts. Otherwise (i.e. when there is no correct transition) input is rejected.

Machines can't use no-move transitions.

I believe everything else can be found on this article or in Hamkins's paper.

Multicolor machines

I noticed community shows an interest in expension of these machines to multiple colors. I believe this concept wasn't analysed, because these machines are no stronger than 2 color ones. However, they can be used to get bounds on Eternal Emu, Timeless Tiger and Immortal Iguana functions, so I might start considering them. Transition rules are straightforward - normal transitions on successor stages, limsup at limit stages.

Full power (3-tape) machines

Machine tape will consist of 9 symbols: mandatory left-end marker, blank (in this paragraph called 0) and numbers 1-7. Each number will represent bits on 3 tapes - first bit is input tape's cell, second bit is from scratch tape and third bit represents output. Input will be coded as usual: using 0's and 1's (and #, of course). Output, however, will be coded as following: numbers 0-3 mean blank on output tape, and 4-7 mean 1 on output. Transitions at successor stages are as usual, according to machine's program. Limit stages are more tricky - we have to take limsups of individual bits: if we have cell with numbers 1,2 appearing infinitely many times, bitwise limsup will be 3 - first bit and second flash infinitely many times, so at limit both will be on.

1-tape programs

This is where everything will happen!

\(\omega\) steps

We have to start somewhere, right? Machine halts whenever it enters limit state.

* # * r *

0 _ _ r 0
L _ _ r halt

\(\omega^2\) steps

I believe this is longest lasting machine with one state, estabilishing \(\gamma[1]=\omega^2\). After every limit stage machine flashes a 1 on the first cell, so it is first 1 at limit stage at \(\omega^2\), then machine halts.

* # * r *

0 _ _ r 0
0 1 _ r 0
L _ 1 l 0
L 1 1 r halt

I'm also making a little competition for a name for machines giving bounds for \(\gamma[n]\), because "transfinite Busy Beaver" sounds a bit too technical to me :)

Write \(\omega\)

Machine was built in parts.

Extractor

This machine will decode number \(\langle a,b\rangle\) into \(a\) and \(b\), separated by 2 blanks. (this is normal Turing machine, not ITTM)

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

\(\in\omega?\)

This machine, given integer \(\langle a,b\rangle\) checks if \(a<b\), that is, if this integer should be marked in real coding \(\omega\). (this is normal Turing machine, not ITTM)

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

15 1 1 r 15
15 _ _ l 16
16 1 _ l 17
17 1 1 l 17
17 _ _ l 18
18 _ _ l 19
19 1 1 l 19
19 _ _ r 20
20 1 _ r 21
20 _ _ r halt
21 1 1 r 21
21 _ _ r 13

Ready machine

Here is, I believe, first in the existence machine which writes down, on empty input, transfinite ordinal!

* # * r *

0 _ _ r 1
1 _ 1 r 2
2 _ 1 r 3
3 _ _ r 4
4 _ 1 r 5
5 1 1 r 5
5 _ _ r 6
6 _ _ r 7
7 _ _ r 11
11 _ _ r 11' ;state recycling & I'm too lazy to relabel states
11' * 1 r a1

8 _ _ l 9
9 1 _ l 9
9 _ _ l 10
10 _ _ l 10
10 1 1 l 10'
10' 1 1 l 10'
10' _ _ l 11
11 1 1 l 12
12 1 _ r 13
13 1 1 r 14
14 _ 1 r 15
15 1 _ r 16
15 _ 1 r 17
16 1 1 r 16
16 _ 1 r 17
17 _ _ r 18
18 _ _ r 19
19 _ _ r 20
20 _ _ r 21
21 _ _ r 22
22 _ 1 l 23
23 _ _ l 23
23 1 _ r 24
24 _ 1 r 25
25 1 1 r 25
25 _ _ r 26
26 _ _ r 26
26 1 1 r 27
27 1 1 r 27
27 _ 1 l 28
28 1 1 l 28
28 _ _ l 29
29 _ _ l 29
29 1 1 l 30
30 1 1 l 30
30 _ _ l 31
31 1 _ r 24
31 _ _ r 32
32 _ 1 r 5

33 _ _ r 34
34 1 _ r 34
34 _ _ l 35
35 1 1 r 36
35 _ _ l 35
36 _ 1 l 37
37 1 1 l 37
37 _ 1 r 38
38 1 _ r 39
39 1 1 r 39
39 _ _ r 18


a0 1 1 r a1
a0 _ _ l a10
a1 1 _ r a0
a1 _ _ l a2
a2 1 _ l a3
a3 1 1 l a3
a3 _ 1 l a4
a4 1 1 r a5
a4 _ _ l a6
a5 1 1 r a5
a5 _ _ l a2
a6 _ 1 r a7
a7 _ _ r a7
a7 1 _ r a8
a8 1 1 r a8
a8 _ 1 l a9
a9 1 1 l a9
a9 _ _ r a1
a10 _ _ l a11
a11 1 _ l a12
a11 _ _ r a15
a12 1 1 l a12
a12 _ 1 l a13
a13 _ _ r a15
a13 1 1 r a14
a14 1 1 r a14
a14 _ _ l a11
a15 1 1 r a15
a15 _ _ l a16
a16 1 _ l a17
a16 _ _ l b0
a17 1 1 l a17
a17 _ _ l a18
a18 _ _ l a19
a19 1 1 l a19
a19 _ _ r a20
a20 1 _ r a21
a20 _ _ r 33
a21 1 1 r a21
a21 _ _ r a13

b0 _ _ l b1 ;tiny subroutine required when number codes <a,a>
b1 _ 1 r 8
b1 1 1 r 8

L _ _ r halt

Here is brief look of how machine works:

  1. We know \(0=\langle0,0\rangle\) doesn't belong to \(\omega\), so we "hard-code" it into machine.
  2. Machine makes quick setup - 2 cells which I call "printer" - they mark where output ends anr workspace begins - and two ones separated by 4 blanks - first of them only sits there and says which number we check, and second one is the one we work on.
  3. We use \(a\) subroutine to check if number belongs to \(\omega\), i.e. if it will be in output.
  4. In either case we erase leftovers of checking and go to printer. If number is in \(\omega\) we leave 1, and we leave 0 if it doesn't.
  5. Now we increase the number we work on.
  6. We make a copy of current number 4 cells to the left.
  7. Repeat from 3.
  8. After \(\omega\) steps halt.

We can now see that number \(n\) will be eventually checked and printer will write down corresponding bit on \(n\)-th place of tape in finite amount of time, so every cell eventually stabilises, so final output will really be \(\omega\). So here is the bound we all have been waiting for: \(\lambda[66]\geq\omega\)! This machine has a lot of room for improvement, but I'm glad with that result. This printer mechanism will work for every relation which is computable on standard TM, which includes all recursive ordinals (before any questions: I'm not planning on making a machine writing \(\omega_1^\text{CK}\))

\(\omega2\) steps

* # * r *

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

\(\omega2+1\) steps

* # * r *

0 _ _ r 0
0 1 _ r halt
L _ 1 r 0
L 1 _ l 0

I think these are all "interesting" 1-state ITTMs.

\(\omega^3\) steps

After every limit stage machine in state 1 looks into second cell. If there there is nothing there we just flash. because of this, at the limit of limits there will be 1 in that cell. Machine in state 1 then flashes the first cell. It repeats every \(\omega^2\) steps, so at stage \(\omega^3\) first cell is 1, so machine knows it can halt.

* # * r *

0 _ _ r 0
0 1 _ r 0
1 _ 1 l 0
1 1 _ l 1
L _ _ r 1
L 1 _ r halt

The thing with ITTMs is, every machine which takes significantly more than \(\omega\) steps is not simulateable - it's just a thought experiment. And it's not easy to write that such experiment so that everyone will understand.

3-color machine (by Wythagoras)

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

\(\omega^\omega\) steps

First cell is master flag. It flashes roughly at stages \(\omega,\omega^2,\omega^3,...\) so that it is 1 at limit stage for the first time at \(\omega^\omega\). To achieve this we use series of flags, such that the first one flashes every \(\omega\) steps. When we see it is 1 after limit stage, \(\omega^2\) steps must have passed, so we flash the second flag. And so on. One cell before a flag there is check cell - if we read check cell and it's blank, we know that it's the first time we are going to flash this flag. So we go flash the master flag. And this repeats. At stage \(\omega^\omega\) master flag is 1, so we can halt the machine.

* # * r *

0 _ 1 l 0
0 1 _ r 1
1 1 1 r 2
1 _ 1 l 5
2 1 _ r 1
2 _ 1 l 3
3 1 1 r 4
3 _ _ r 4
4 1 _ r 3
4 _ _ r 3
5 _ _ l 6
6 1 1 l 5
6 _ 1 l 0
L _ _ r 1
L 1 1 r halt

3-color machine (by Deedlit)

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

3-color machine (by Wythagoras)

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

\(\omega^{\omega2}\) steps

My above machine works sort of like base-\(\omega\) counters - each flag has imaginary counter which counts number of flashes, and when it hits \(\omega\) we flash the next one. Above machine halts after we use \(\omega\) of these. Now imagine we use \(\omega2\) counters - we arrange them in following manner: 0,ω,1,ω+1,2,ω+2,... On tape we have simply \(\omega\) of these, but at first we use every second of them. Second cell of tape is used as secondary master flag, which is 1 after every \(\omega^\omega\) steps. It indicates when to use our "transfinite" counters.

* # * r *

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

15 1 1 r 16
16 1 1 r 17
17 _ 1 l 18
17 1 1 r 22
18 1 1 l 18
18 _ _ l 19

19 1 1 l 18
19 _ 1 l 20
20 1 _ r 21
21 * * r 21
22 _ 1 l 23
22 1 _ r 15
23 1 1 r 20

L _ _ r 1
L 1 1 l halt

Using this series of master flags we can extend this fairly easily to \(\omega^{\omega n}\). Next step - \(\omega^{\omega^2}\)

3-tape programs

\(\omega^4\) steps

I believe this is the best we can do with 1 state. At limit stages we flash flag at input tape. At compund limit stages we flash flag on input tape. At limits of compound limit stages we flash flag on output tape. Finally, at stage \(\omega^4\), we can halt.

* # * r *
0 # * r 0

0 * _ r 0
L _ 1 l 0
L 1 3 l 0
L 3 7 l 0
L 7 _ l halt

\(\omega^4+4\) steps

Found during our discussion on chat

* # * r *

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

L _ 1 l 0
L 1 3 l 0
L 3 7 l 0
L 7 6 l 0

\(\omega^\omega\) steps

It works just like one-tape version of this machine, expect for check cells being on scratch tape, right below corresponding flag on input tape.

Thanks to Wythagoras, who noticed one can combine states 0 and 3 (using old labels), thus reducing number of states.

* # * r *

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

\(\omega^{\omega+2}\) steps (by Wythagoras)

* # * r * 
  
0 _ _ r 1  
0 1 _ r 1 
0 3 _ r 0 
0 7 _ r 0
1 _ 1 l 2  
1 1 3 l 3  
1 3 1 r 1  
2 1 1 l 2  
2 _ 1 l 0  
3 _ _ r 3  
3 1 1 r 3  
3 3 1 r 3  
L _ _ r 0  
L 1 3 l 0 
L 3 7 l 0 
L 7 _ r halt

Bounds

Thanks FB100Z for awesome silly names! (subscripts mean color count)

1-tape machines

Eternal Emu function

\(\lambda[66]\geq\omega\)

Timeless Tiger function

\(\gamma[1]=\omega^2\)

\(\gamma[7]\geq\omega^\omega\)

\(\gamma[24]\geq\omega^{\omega2}\)

\(\gamma[1]_n\geq\omega^n\), \(\gamma[4]_3\geq\omega^\omega\) (bounds by Wythagoras)

\(\gamma[2]_n\geq\omega^{2n-1}\) (bound by Deedlit)

\(\gamma[2]\geq\omega^3\)

Immortal Iguana function

Imagine the output on the tape of a machine has eventually stabilized. Because the output is the only tape we have, it means that no cell on this tape will ever change again. But this means that machine will loop with period of \(\omega\) - if machine is in limit state, and changes nothing in the following \(\omega\) steps, it will repeat the configuration. Even worse, it is semi-decidable if this situation ever happens: we can simulate two of the same machine at once, but one simulation with \(\omega\) steps of delay. At every limit stage we check if configuration is the same. If it is, then we check if in the following \(\omega\) steps machine makes any changes. If not, then machine eventually stabilised, so we halt with affirmative answer. Conclusion: eventually one-tape writable ordinals are one-tape writable. So making up Immortal Iguanas is fairly meaningless.

3-tape machines

Eternal Emu function

Timeless Tiger function

\(\gamma[1]\geq\omega^4+4\), \(\gamma[4]\geq\omega^{\omega+2}+20\) (improved bounds by Wythagoras)

Immortal Iguana function

References

  1. Infinite time Turing machines with only one tape

Ad blocker interference detected!


Wikia is a free-to-use site that makes money from advertising. We have a modified experience for viewers using ad blockers

Wikia is not accessible if you’ve made further modifications. Remove the custom ad blocker rule(s) and the page will load as expected.