튜링 기계의 계산을 설명합니다.

Question

이 튜링 기계가 실제로하는 일을 해석하는 데 문제가 있습니다 (즉, 영어로 설명하는 방법을 잘 모릅니다).

난 I 올바르게 I는 (이 중 100 %에 있음)가 주어 천이 테이블을 이용 상태도를 작성한 믿는다. 입력 폼

(a || b || B)*Ba*c(a || b || c || B)*의 때마다 I은 수용성 상태 (q2)에서 멈춘다이 TM을 볼 수있는 것과

, a 년대, b 년대 및 블랭크 중 어느 양인

(그러나 c은 없음), 적어도 하나의 공백, 임의의 수의 a 및 정확히 하나의 c이옵니다. 먼저 c을 찾을 때 왼쪽으로 간 이후로 아무 것도 올 수 없습니다.

내 질문

가) 내 작품까지이 시점에 맞 겠지?

b)이 튜링 기계에 대한보다 의미있는 설명이 있습니다 (즉, 내가 입력 한 내용이 (q2)에 기록 된 것보다 더 풍부한 설명).

Answer 1

일부 관찰 : 그것은 C를 칠 때

1. Q0가 왼쪽에서 오른쪽으로 읽기는 테이프를 변경, 정지하지 않습니다.
2. q1은 왼쪽에서 오른쪽으로 읽으며, a와 b를 바꿔주고, B를 볼 때 멈추고, a에 부딪 힐 때 뒤집습니다.
3. • 는 AC 초기 테이프 위치의 오른쪽에있는 테이프 어딘가에있을 경우 TM을 중단 할 수있는 유일한 방법은 1 분기
   • , 오른쪽에서 왼쪽으로 최종 패스 만 B 본다 c의 왼쪽에는 첫 번째 c와 오른쪽 B 사이에 a 만 남습니다.
4. Q1은 AB에 그 C의 왼쪽에 제 (C) 및 우측 (B) 사이의 모든 변경 결국

초기 테이프 구성> BxBycz는 기계가 항상 구성 멈춘다 감안> BXB (a^| y |) cz. c를 포함하는 문자열을 모두 허용합니다.

귀하의 상태 다이어그램은 테이블이 f (q1, a) = (q0, b, L) 및 f (q1, b) = (q1, a, L)), 다이어그램은 f (q1, a) = (q1, a, L) 및 f (q1, b) = (q0, b, L)를 보여줍니다.