단어를 바꾸지 않고 단일 테이프 튜링 기계에서 회문을 찾는 것

Question

(Φ)를 사용하여 양 끝에 palindrome replacement letters를 찾는 것은 꽤 쉽습니다.

ΦabaΦ 
ΦΦbaΦ 
ΦΦbaΦ 
ΦΦbaΦ 
ΦΦbaΦ 
ΦΦbaΦ 
ΦΦbΦΦ 
ΦΦbΦΦ 
ΦΦbΦΦ 
ΦΦΦΦΦ 
ΦΦΦΦΦ 
ΦΦΦΦΦ YES 

a를 a로 변경하고 작업 끝에서 A를 a로 변경할 수 있습니다. 그러나 아무도 아이디어가 있습니까? 추가 표지판을 사용하지 않고이를 달성하는 방법은 무엇입니까?

Answer 1

a를 a로, b를 B로, ur 끝 문자를 대문자로 변경할 수 있습니다. (ascia 값을 취하고 대문자 범위에 속하면 끝을 알게 됨) 입력 내용이 전적으로 소문자라고 가정합니다.

Answer 2

테이프의 가능한 기호 (유한 집합에서 가져온 것으로 가정)에 대해 "$ X_LOOKING"이라고하는 상태가 필요합니다. 왼쪽 끝에서 시작하여 거기에있는 기호 $ X에 대해 "$ X_LOOKING"으로 상태를 설정하십시오. 끝까지 충돌 할 때까지 오른쪽으로 이동하여 $ X와 일치하는지 확인합니다.

왼쪽 뒤로 이동하면 두 번째 문자 대신 첫 번째 문자로 이동해야합니다. 이 경우 테이프의 다른 영역에서 몇 자 보았는지 추적 할 수 있습니다.

Answer 3

도움이 될 수 있습니다 끝 문자로 이동 :

ΦΦabaΦΦ 
ΦaΦbaΦΦ 
ΦaΦbΦaΦ YES 

또는

ΦΦabbaΦΦ 
ΦaΦbbaΦΦ 
ΦaΦbbΦaΦ 
ΦabΦbΦaΦ 
ΦabΦΦbaΦ YES