튜링 기계 번호가

Question

http://morphett.info/turing/turing.html

가 어떻게 같은 반복 번호 순서를 만들 것 시퀀스 생성 : ...

01011011101111011,111

그래서 기본적으로 1을 추가 한 후, 0을 추가 한 후 제로 , 그 다음 이전 수의 1의 위에 1.

Answer 1

테이프에 01을 작성하십시오. 한 칸 오른쪽으로 이동하십시오. 0을보고 있으면 0이 보일 때까지 왼쪽으로 다시 스캔하십시오. 한 칸 오른쪽으로 이동하십시오. 하나를보고있는 경우, 2로 바꾸고 0으로 보일 때까지 오른쪽으로 이동하십시오. 다음으로 움직일 때까지 계속 움직여야합니다. 이 0을 1로 바꾸십시오. 그런 다음 두 개가 나타날 때까지 뒤로 이동하십시오. 두 개를 하나로 교체하십시오. 하나는 오른쪽으로 이동하십시오. 당신이 하나를보고 있다면, 2로 교체하고 다시 돌아가는 과정을 반복하십시오. 결국, 당신은 1의 이전 공급을 다 써버 릴 것이므로, 오른쪽으로 움직일 때 0을 보게됩니다. 이 경우, 다음 0으로 오른쪽으로 이동하고이를 1로 바꾸십시오. 이 과정 전체를 루프하면 ("01 쓰기") 더 긴 문자열을 얻을 수 있습니다.

직감은 직설적입니다. 오른쪽으로 이동하면 0이 표시되고 두 번째는 0으로 이동하고 copy 0 점을 찾은 후 마지막 점과 마지막 점 사이의 모든 점을 찾은 다음 하나를 더 추가합니다. 두 점은 복사하려는 문자열의 위치를 ​​추적하는 방법으로 사용됩니다. 기본적인 아이디어는 소리,하지만 당신은 그것을 엄격하게 이것에 대한 상태 및 전환을 작성하려고한다

예 :.

> 
^ 
>0 
^ 
>01 
^
>010 
^
>010 
^ 
>010 
^
>020 
^
>0200 
    ^
>0201 
^
>0201 
^
>0101 
^
>0101 
    ^
>01010 
    ^
>010110 
    ^