2011年10月19日水曜日

Turing Machine

I read "BEYOND REASON".
I don't know about Turing Machine, but this is quite interesting because I can still find the similarity with web programing in these days. I also count prime numbers, so I can study from the algorithm of Turing Machine. The realm is completely different. However, it seems to be a new light for me.

Turing Machine is like an infinite tape. It read a sign from each cell.
For example, there are three cells, such as 0(zero),1,X.





0

1

X

A

0NA

1NA

XRB

B

0RB

1RB

0RC

C

XLD

XLD

XLD

D

0LD

1LD

XNE

E

Stop

Stop

Stop


This is like a dictionary or code.
0="Put 0 in the cell". 1="Put 1 in the cell". N="Don't move the cell". A="Stay in the same cell". X="Put X in the cell". R="Move the cell to the right". B="The new state". C="The end of the line.Then put X". L="Move the cell to the left". D="The new state". E="The end".

When you see A, there are three cells such as 0=(0NA), 1=(1NA), X=(XRB). 0NA means that put 0 in the cell and don't do anything. 1NA means that put 1 in the cell and don't do anything. XRB means that put X in the cell and move it to the right for a new state.
After you put X in a cell, you can go to B.
In B, there are 0=(0RB) 1=(1RB) X=(0RC).
You can adjust the same pattern from the dictionary, then you see that C means the end. However, you put X, so the line don't stop. It goes to C.
In C, it moves to the left which means the reverse.
Finally, you see the end in D,X=(XNE).
However, if you don't put XNE and you increase cells like D1,D2,D3・・・, Turing Machine may never stop for ever.