튜링머신 예제

    질문 : 단일 테이프 튜링 머신 M은 q0이 시작 상태인 두 개의 상태 q0 및 q1을 가지고 있습니다. M의 테이프 알파벳은 {0, 1, B}이고 입력 알파벳은 {0, 1}입니다. 기호 B는 입력 문자열의 끝을 나타내는 데 사용되는 빈 기호입니다. M의 전환 함수는 다음 표에 설명되어 있습니다. 튜링 기계의 동작은 원자가 아니기 때문에 기계의 시뮬레이션은 각 5튜플을 더 간단한 동작의 시퀀스로 분무해야 합니다. 그의 기계의 „행동“의 다음 예에서 사용되는 한 가지 가능성은 다음과 같습니다: 비종료 튜링 기계. 이론적 관점에서 볼 때, 우리는 주로 유한한 계산을 수행한 다음 중단하는 기계에 관심을 가지고 있습니다. 그러나 많은 실용적인 응용 프로그램은 종료하지 않는 프로그램 (운영 체제, 항공 교통 관제 시스템, 원자로 제어 시스템) 또는 출력의 무한한 양을 생성하도록 설계 된 프로그램을 포함 (웹 브라우저, π의 숫자를 계산하는 프로그램 = 3.1415…). 튜링 기계 계산 모델은 이러한 비종료 상황을 처리하기 위해 확장됩니다. 튜링의 진술은 여전히 다섯 가지 원자 작전을 암시한다. 주어진 명령(m-구성)에서 컴퓨터: 실행. 처음에 튜링 머신은 시작 상태라는 하나의 고유 한 상태에서 시작하고, 테이프 헤드는 시작 셀이라는 하나의 고유 셀을 가리킵니다. 상태 및 입력 기호의 각 조합에 대응하는 최대 하나의 가능한 전환이 있습니다.

    따라서 기계의 동작은 사전에 완전히 결정됩니다. (일부 입력 기호가 있는 상태에서 전환이 불가능한 경우 튜링 머신은 동일한 상태로 유지되고 입력 기호를 덮어쓰지 않습니다.) 튜링 머신의 각 단계는 다음과 같이 진행됩니다 : 우리의 프로그램에 더 많은 상태의 도입으로, 우리는 튜링 기계가 더 복잡한 기능을 수행하도록 지시 할 수 있으며, 따라서 현대 컴퓨터가 할 수있는 모든 알고리즘을 실행할 수 있습니다. 컴퓨터가 실제로 수행하는 동작과 관련하여 튜링(1936) (undecidable p. 121)은 다음과 같은 상태를 표시합니다. 그 작업은 그들 사이에 0을 작성하여 테이프에 발생하는 1s의 시리즈를 두 배로하는 것입니다. 예를 들어 헤드가 „111“을 읽으면 0을 작성한 다음 „111“을 씁니다. 출력은 „1110111“이 됩니다. 튜링 기계는 1936년 수학자 앨런 튜링이 생각한 가상의 기계입니다. 단순함에도 불구하고 기계는 아무리 복잡한 컴퓨터 알고리즘을 시뮬레이션 할 수 있습니다! 튜링 기계 시뮬레이터. 이것은 밥 세지윅과 케빈 웨인의 감독하에 톰 벤티밀리아가 자바로 작성한 그래픽 튜링 머신 시뮬레이터입니다. 그러나 이 작업을 수행하는 더 간단하고 틀림없이 더 많은 „튜링 머신 스타일“방법이 있습니다.

    As의 모든 Xs로 덮어쓰면 튜링 머신은 모든 X를 지웁니다(#s 덮어씁니다). 튜링 머신은 0형식 문법에 의해 생성된 언어(재귀적으로 열거 가능한 집합)를 수락하는 수락 장치입니다. 그것은 앨런 튜링에 의해 1936 년에 발명되었다. 3 상태 바쁜 비버의 전체 „실행“. 결과 튜링 상태 (튜링이라고 무엇 „m-구성“- „기계 구성“) 열 A에서 회색으로 강조 표시하고, 또한 기계의 지침 (열 AF-AU)에서 표시: 지침의 다음 튜링 테이블은 파생되었다 피터슨 (1988) 페이지 198, 그림 7.15에서. 피터슨은 머리를 움직인다. 다음 모델에서 테이프가 이동합니다. 표를 자세히 살펴보면 튜링의 모범에 대한 특정 문제가 드러납니다. 어리석은 것처럼 보이지만 이제 이미 반전 된 비트 „1 1 0″을 „0 1″에서 „1 1 0″으로 되돌리는 추가 상태를 프로그램에 추가해 보겠습니다.

    다음은 기울임꼴로 나열된 변경 내용과 함께 업데이트된 테이블입니다. 튜링 기계는 이제 두 개의 상태를 가진 유한 상태 기계처럼 작동하며, 이를 세 가지 기호, 2상태 튜링 머신이라고 합니다.