0을 계산하고 2 진수가 얼마나 많은지를 계산하는 튜링 기계 알고리즘

Question

0의 문자열을 읽은 다음 튜너에 얼마나 많은 바이너리가 있는지 튜링 기계에 알고리즘이 필요합니다.

실제로 기계가 실제로 0을 계산하지 않을 것이라는 것을 알고 있지만 어떻게해야하는지 잘 모르겠습니다.

나는 먼저 이진수가 X 나 다른 것으로 시작하는 곳을 표시해야한다. 그런 다음 가장 중요한 비트가 1이면 0을, 1이면 0을 쓰면된다. 0이되면 1이되지만 1이면 어떻게됩니까? 어쩌면 그것을 0으로 돌리고 1을 0으로 만들 때까지 모든 1을 튜닝하고 0을 유지하거나 공백으로 1을 만들 때까지 계속 가야합니까? 그럼 다시,이 경우에 같은 일에 관계없이 년대 LSB 내가 같은 일을 할 것 때문 만 0 ...

흠 ... 고무 duckie 첫 번째 위치 것

Answer 1

편집 : 나는 Bainville에게 양보한다.

나는 지난 밤에하고 싶은 것을 알아 냈고 두 개의 분리 된 튜링 기계와 아마 속임수를 쓰겠습니다.

제 시스템의 헤드 입력 테이프상에서 실행하고 그것은 0

번째 시스템은 단순히 가산 기계가 될 것이고, 이는 현재의 수에 1을 추가 스캔 경우 단순히 제 컴퓨터를 시작할 것 상당히 쉽게 할 수 있습니다. 그냥 길게 추가되었으므로 나머지가 있다고 말하는 상태를 만들고 0에 도달 할 때까지 왼쪽으로 계속 이동하거나 1로 바꾸거나 빈 자리를 찾아서 1을 만듭니다.

Bainville가 내 투표에서 이깁니다.

Answer 2

는 입력 테이프 초기 판독 위치가 끝 # 발생한 0 수 (초기에 0의 패리티를 유지 도달 오른쪽까지

0 제

1. 움직임이다 #00000000000#이다 가정 1, 0, ...). 각 쌍의 첫 번째 0을 -으로 바꿉니다. - 읽기는 무시되며 패리티는 변경되지 않습니다.

2. 출력 테이프 패리티 쓰기 왼쪽으로 이동 (순서 비트 쓰기)

3. 복귀 끝에 입력 왼쪽 # 머리, 고토 1

첫 번째 패스의 입력 테이프는 #-0-0-0-0-0-#이고 출력은 1입니다.

두 번째 패스 끝 부분 : #---0---0---# 및 11.

세 번째 패스의 끝에서 : #-------0---# 및 011.

네 번째 패스 끝 부분 : #-----------# 및 1011.

Answer 3

체크 아웃이 튜링 기계 시뮬레이터와 이진 계산 예제 프로그램 :

Uber Turing Machine가 프로그램으로 튜링 기계 할 수 있습니다 - 어떤 컴퓨터의 논리를 시뮬레이션하기 위해 적용 할 수있는 보편적 인 이론적 장치를 연산. 이 소프트웨어 덕분에 새로운 알고리즘을 만들 수 있으며 을 이미 편집 한 사람 을 통해 편집하고 편리한 시각적 IDE를 통해 편집 할 수 있습니다. 이 숙제는