User:Cycwin/maIsTc

MA(markov algorithm) is turing complete. It can simulate the section fourteen point two minsky machine. The string in the start is

/S)|

We call the letter S a state. mul a number(use 2) when thr state is m:

m) -> m)m)

Now we call this command 'mul x'. div a number(use 2) when the state is s, if the register / 2(because we use 2) is an integer, switch the state to N, if not, let register be register * 2(because we use 2) and switch the state to tT.

s) -> S)
S)S) -> R)
/R)| -> /N)|
R)R)| -> N)N)|
R)N) -> N)N)
S) -> tT)
R)tT) -> tT)tT)tT)

if the number is not two we only need to change two lines: Line 1 and 6. if div by n, repeat S) n times in line 1 and repeat tT) (right hand) n+1 times. Now we call this command 'div x,A,B'.(A is N in the example)

About minsky machine, any program like this:

:l
mul 2
mul 3
div 5,l
mul 7
div 7,m
mul 11
halt(we can use ') -> ]')
:m
mul 13
halt

Can convert to many structures like:

:l
mul 6
div 5,l,A
:A
mul 7
div 7,m,M
:m
mul 13
halt
:M
mul 11
halt

A state can run a mul command then a div command or halt.(cant mul after div.) Just like:

:state
mul x
div a,m,n(halt)

And many this kind of structures can be a normal 14.2 minsky machine program. Well, because the section 14.2 minsky machine is tc, MA is TC.