튜링 기계가 테이프의 시작 부분을 지나갈 수 있습니까?

Question

터닝 머신에 대한 간단한 질문이 있습니다.

테이프를 되감기가 포함 된 첫 번째 동작이 시작점을지나 뒤로 이동합니까? 아니면 특수한 경우이며 시작점에 남을까요?

Answer 1

튜링 기계의 테이프는 양방향 모두 무한대입니다. 일반적으로 처음 이전의 모든 내용은 0으로 채워져 있다고 가정합니다.

Answer 2

테이프는 방향 에서 무한히 확장 가능합니다. 방향입니다. Wikipedia은 다음과 같이 말하고 있습니다 :

테이프는 셀로 나누어지고, 하나는 다른 셀로 나뉩니다. 각 셀에는 유한 한 알파벳의 기호가 있습니다. 알파벳에는 특별한 공백 기호 (여기서는 'B'로 쓰여 있음)와 하나 이상의 다른 기호가 들어 있습니다. 테이프는 좌측 및 우측으로 임의로 연장 될 수있는 것으로 가정된다. 즉, 튜링 기계는 계산에 필요한만큼의 테이프가 항상 제공된다.

Answer 3

정말 어떤 형식을 사용하고 있는지에 따라 다릅니다. 일부 형식주의는 테이프가 양방향으로 무한히 확장 가능하고 다른 테이프는 왼쪽 끝이 있습니다. 왼쪽 끝 캠프 안에는 여전히 더 많은 구획이 있습니다. 어떤 사람들은 테이프가 왼쪽 끝에서 벗어 났을 때 기계가 작동하지 않거나 생산량을 산출하지 못한다고 말한다. (햄킨스와 미스 니코프가 확률을 낮추라고 생각하고있다.) 다른 사람들은 가장 왼쪽의 테이프 셀에 특수하고 재기록 불가능한 마커를 강요한다고한다. (Kozen은 그의 Automata and Computability 교과서에서 이것을 수행한다). 이러한 형식주의는 모두 본질적으로 동등하므로 대부분의 사람들은 그것에 대해 큰 관심을 두지 않고 현재 사용중인 응용 프로그램에 가장 편리한 것을 사용합니다.