| [ QuizWit ] in KIDS 글 쓴 이(By): monoid (free) 날 짜 (Date): 1994년03월14일(월) 23시52분18초 KST 제 목(Title): 튜링머신이란... 저도 튜링머신에 대해 별로 아는 것은 없지만, 정의정도는 어떻게 써 볼 수 있을 것 같네요. 튜링머신에는 변종이 많이 있기 때문에 어느 것을 꼬집어서 말하기는 어렵지만 (튜링이 처음에 발표한 형태가 궁금하군요) 정의는 그다지 복잡하지 않습니다. 머신은 유한개의 state와 유한개의 기호(symbol)을 갖습니다. 기호중 특별한 한 개는 공백(blank)라고 부릅니다. 상태중 특별한 두 개는 각각 시작과 끝이라고 부릅니다. 또 머신을 기술하는 마지막 요소는 이동규칙입니다. 이것은 현 상태와 방금 읽은 기호의 함수인데, 그 함수값으로 다음 세 가지의 순서쌍을 갖습니다. 1)다음 상태 2)지금 있는 자리에 남겨둘 기호 3) 헤드를 어느쪽으로 움직일 것인지 그 여부, 즉, 오른쪽, 왼쪽, 제자리 중 하나 머신은 한쪽 방향으로 유한한 길이의 테이프를 갖습니다. 머신이 어떤 단어를 받아들인다는 것은 다음과 같습니다. 처음 머신이 시작할 때는 테이프 위에 그 단어가 왼쪽 끝에서부터(오른쪽으로 무한하다고 합시다) 적혀 있고, 나머지는 모두 공백으로 차 있습니다. 헤드는 왼쪽 맨 끝에서 시작합니다. 상태는 시작 상태입니다. 헤드는 현재 위치에 적혀있는 기호를 읽고, 이동 규칙에 따라 상태를 바꾸고, 지금 있는 자리에 새 기호를 남기고, 헤드를 이동합니다. 그러다가 상태가 앞에 언급한 끝 상태에 도달하면 그 단어는 받아들여진 것입니다. (단 하나 문제가 되는 것은, 헤드가 왼쪽 끝으로 '떨어져 버리는' 경우인데, 이때는 받아들이지 않은 것으로 하기로 합시다.) 튜링 머신에는 많은 변종이 있을 수 있습니다. 테입을 양방향으로 무한하게 만드는 수도 있고, 헤드가 정지하는 것을 허용하지 않을 수도 있습니다. 테입을 2개 이상 만들 수도 있고, 멈추기 전에 최종적으로 테입 위에 남아 있는 결과를 일종의 계산 결과로 보는 수도 있습니다. 그래서, 일반적으로 이런 튜링 머신을 가지고 사칙 연산이나 power계산 등을 하기 위해서는 믿을 수 없을 정도로 많이 헤드가 좌우로 왔다갔다해야 합니다. monoid |