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) then change state to M when the state is m:

m) -> M)M)

Now we call this command 'mul x,M'. div a number(use 2 for an example) when the state is S, if the value of register / 2(because we use 2) is an integer, change the state to N, or let register be the value of register * 2(because we use 2) and change the state to tT.

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 2 we only need to change "2"s in two lines: Line 1 and 6. if you want the value of register to div by n(an integer), just repeat S) n times in line 1 and repeat tT) (in the 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

(Because We can think of mul and a div(halt) as a structure. After mul switches to the M state, we can perform div operations in the M state.) A state can run a mul command then a div command or halt.(you 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.

Using BCT

We need a string before our code:

K1 -> 1K
K0 -> 0K
KE -> 0E
P1 -> 1P
P0 -> 0P
PE -> 1E

Let us call the first "state" Q and last "state" D. Add string

Q -> E

after the string.

Let us call using state N and next state R BCT's 0:

N1 -> R
N0 -> R

BCT's 10:

N -> RK

BCT's 11:

N -> RP

BCT is TC. MA is TC.