tautonyms를 확인하기 위해 one-tape, two-head TM을 어떻게 설계 하시겠습니까?

Question

이 언어가 무엇인지 알아야합니다.

L = {ww | w {0,1} *}

은 튜링 기계로 결정할 수있다. TM에는 1 개의 테이프와 2 개의 헤드/포인터가 있습니다. 입력 문자열은 유한입니다. 그것을 해결하는 방법에 대한 제안?

문자열의 길이를 알면 쉽게 해결할 수 있습니다.

Answer 1

힌트로, 빠른 테이프 헤드가 문자열에서 벗어날 때까지 한 테이프 헤드를 앞으로 2 단계 앞으로 앞으로 움직이고 다른 한 단계 앞으로 앞으로 이동하여 문자열의 중간 점을 찾을 수 있습니다. 그 시점에서 느린 테이프 헤드가 중간 지점에 있습니다. 그 문자열에서 중단 점을 찾는 데 도움이 될 수 있습니다.

희망이 도움이됩니다.