태그 시스템
태그 시스템(영: Tag system)은, 1943년에 에밀・포스트가 발표한 결정성 계산 모형의 일종이며, 포스트정 준계의 극히 단순한 형식의 것이다.태그 시스템을 추상 기계로 간주했을 경우, 포스트태그 기계(Post Tag Machine, PTM)라고도 부른다.대략적으로 말하면, 무한장의 FIFO 큐로서의 테이프 장치를 가진 유한 상태 기계이며, 상태 천이마다 테이프의 헤드 위치로부터 기호를 읽어내, 헤드 위치로부터 고정개의 기호를 소거해, 최후미에 기호를 추가한다.
목차
정의
태그 시스템은 세 개 한벌(m, A, P)로 나타내져 각각은 이하의 의미를 가진다.
- m -정의 정수이며, 삭제수(deletion number)라고 부른다.
- A -기호군의 유한 알파벳.그 중의 하나가 특별한 정지 기호(halting symbol)이다.A로 구성되는(하늘도 포함한다) 유한의 문자열을 단어(words)라고 부른다.
- P -생성 규칙군.A에 포함되는 개개의 기호 x에 적용하는 것을 P(x)로 나타낸다(생성한다고도 부른다).정지 기호에의 생성 규칙의 적용(P(H))는 후술 하도록(듯이) 계산에는 아무 의미도 없지만, 편리성이기 때문에 P(H) = H로 여겨진다.
m-태그 시스템이라고 했을 경우, m는 삭제수를 가리킨다.태그 시스템의 정의는 서적에 따라서 다르지만, 여기서의 설명은 Rogozhin의 것에 준하고 있다.
- 정지 단어(halting word)란, 정지 기호로 시작되는 단어인가, 길이가 m미만의 단어이다.
- 변환 t(태그 조작이라고도)는, 정지 단어 이외의 단어에 대해 정의되고 있어 단어 S의 좌단의 기호를 x로 했을 때, t(S)와는 S의 좌단으로부터 m개의 기호를 삭제해, 남은 부분의 우측으로 단어 P(x)를 추가한 것이다.
- 태그 시스템에 있어서의 계산이란, 변환 t를 반복하는 것으로 유한 단어열을 생성하는 것이어, 초기 상태로 어떠한 단어가 주어져 정지 단어가 생성된 시점에서 정지한다.덧붙여 이 정의로는, 유한회의 반복동안에 정지 단어가 생성되지 않는 경우를 계산이라고는 부를 수 없다.
이 정의로 정지 기호를 사용하면, 계산 결과적으로 마지막 단어만을 출력한다.한편, 정지 기호를 사용하지 않으면, 태그 조작의 반복에 의해서 생성된 단어열전체가 출력이 된다.
전형적인 다른 정의로서 정지 기호를 사용하지 않고, m미만의 길이의 단어를 모두 정지 단어로 하는 정의도 있다.또, 포스트가 1943년에 최초로 발표한 정의로는, 공문자열에 대한 봐 정지하게 되어 있었다.
례: 단순한2-태그의 예
정지 기호를 사용한 단순한2-태그 시스템의 예를 이하에 나타낸다.
2-태그 시스템 알파벳: {a, b, c, H} 생성 규칙: a --> ccbaH b --> cca c --> cc 계산예 초기 단어: baa acca caccbaH ccbaHcc baHcccc Hcccccca (정지) 례: 코랏트 수열의 계산
다음2-태그 시스템(정지 기호를 사용하지 않고, 2 미만의 길이의 단어에 대해 정지)은, C(n) = (n가 짝수라면 n/2아니면(3 n+1)/2)이라고 하는 형식의 코랏트 함수로부터 코랏트 수열을 계산한다(참고 문헌의 De Mol 참조).
이 태그 시스템으로는, 정의 정수 n를 n개의 a를 반복한 단어(aa...a)로 나타낸다.
2-태그 시스템 알파벳: {a, b, c} 생성 규칙: a --> bc b --> a c --> aaa 계산예 초기 단어: aaa <--> n=3 abc cbc caaa aaaaa <--> 5 aaabc abcbc cbcbc cbcaaa caaaaaa aaaaaaaa <--> 8 aaaaaabc aaaabcbc aabcbcbc bcbcbcbc bcbcbca bcbcaa bcaaa aaaa <--> 4 aabc bcbc bca aa <--> 2 bc a <--> 1 (정지) m-태그 시스템의 튜링 완전성
임의의 m > 1인 m에 대해서, m-태그 시스템의 집합은 튜링 완전하다.즉, 어느 튜링 기계 T에 대해서, T를 시뮬레이트 하는 m-태그 시스템이 반드시 존재한다.특히,2-태그 시스템으로 만능 튜링 기계의 시뮬레이트가 가능하다라고 하는 것이, Wang(1963년)과 Cocke & Minsky(1964년)로 나타나고 있다.
반대로, 어느 튜링 기계로 튜링 완전한 m-태그 시스템의 클래스를 시뮬레이트 할 수 있는 것을 나타내는 것으로, 그것이 만능 튜링 기계인 것을 나타낼 수 있다.예를 들면, Rogozhin(1996년)는2-태그 시스템의 클래스의 만능성을 증명했다.이 때의2-태그 시스템의 알파벳은{a1, ..., an, H}, 생성 규칙은{ananW1, ..., ananWn－1, anan, H}, Wk는 하늘이 아닌 단어이다.그리고 그는, 이 태그 시스템의 클래스를 매우 작은(4 상태, 6 기호)의 튜링 기계로 시뮬레이트 할 수 있는 것을 나타내, 그것이 만능성을 가지는 것을 증명했다.
최초의 태그 시스템의 정의
상술의 정의는, 포스트가 1943년에 발표한 당시의 것과는 다르다.포스트의 정의로는 정지 기호가 없고, 하늘의 단어에 대한 봐 정지하게 되어 있고, 태그 조작 t는 다음 같게 정의되고 있었다.
- 하늘이 아닌 단어 S의 좌단의 기호를 x로 했을 때, t(S)는 최초로 단어 P(x)를 S의 오른쪽으로 추가해, 다음에 좌단으로부터 m개의 기호를 삭제한다.기호수가 m개미만이라면, 전기호를 삭제한다.
밑줄을 그은 부분은, m-태그 시스템의 튜링 완전성을 고려한 것이다.
「태그」의 유래
포스트의 1943년의 논문의 각주에 의하면, B. P. Gill이 선두의 m개의 기호를 지우지 않고 남기고 있던 초기의 무렵 시사한 명칭으로, 그 때는 현재 위치를 나타내기 위해서 테이프에 표시를 해 스텝 마다 그 표가 m개만큼 오른쪽으로 이동한다고 하고 있었다.이 때, 표가 문자열의 최후미에 도달했는지의 판정 문제를"problem of tag"이라고 명명했다.이것은, 이른바 술래잡기(영어로 game of tag)가 유래이다.
순환 태그 시스템
태그 시스템을 수정한 순환 태그 시스템(cyclic tag system)이라는 것이 있다.알파벳은 0으로 1만으로부터 되어, 생성 규칙은 단어의 순환 리스트가 되어 있고, 그것을 차례차례 적용해 마지막 단어를 적용하면, 다음은 선두로 돌아온다.좌단의 기호가 1이면, 그 때의 생성 규칙에 나타난 단어를 오른쪽으로 추가해, 0이면 아무것도 추가하지 않는다.어느 쪽의 경우도 좌단의 기호를 1개만 삭제한다.문자열이 비우면 시스템이 정지한다.
예
순환 태그 시스템 생성 규칙: (010, 000, 1111) 계산예 초기 단어: 11001 생성 규칙 단어 ---------- -------------- 010 11001 000 1001010 1111 001010000 010 01010000 000 1010000 1111 010000000 010 10000000 . . . .
순환 태그 시스템은, Matthew Cook이 스티븐・울프 램아래에서 일하고 있었을 무렵에 고안 해, Cook은 이것을 사용해 룰 110 셀・자동 장치가 만능성을 가지는 것을 나타냈다.그 열쇠가 된 것은, 순환 태그 시스템이 튜링 완전한 태그 시스템의 클래스를 에뮤레이트 할 수 있다고 하는 점이었다.
순환 태그 시스템에 의한 태그 시스템의 에뮬레이션
알파벳{a1, ..., an}와 생성 규칙{P1, ..., Pn}로부터 되는 m-태그 시스템은, m*n개의 순환 리스트(Q1, ..., Qn, -, -, ..., -)의 순환 태그 시스템으로 에뮤레이트 할 수 있다.다만, 리스트의 선두 n개 이외는 공문자열('-'로 나타내 보이고 있다)이다.Qk는 Pk에 대응하고 있어, 태그 시스템의 각 기호를 다음 같게 길이 n의 바이너리 문자열로 옮겨놓는 것으로 얻을 수 있다(계산에 임해서는, 초기 단어도 같은 변환이 필요하다).
a1 = 100...00 a2 = 010...00 . . . an = 000...01
즉, ak는 k번째의 위치에 1이 있어, 외는 0인 바이너리 문자열에 encode 된다.따라서, 태그 시스템에 있어서의 1행(1 스텝)은, 순환 태그 시스템으로의(m*n) 행으로 에뮤레이트 된다.
예
이하에 매우 작은 예를 나타낸다.
2-태그 시스템 생성 규칙: (a --> bb, b --> abH, H --> H) 알파벳 encode: a = 100, b = 010, H = 001 생성 규칙의 encode: (bb = 010 010, abH = 100 010 001, H = 001) 순환 태그 시스템 생성 순환 리스트: (010 010, 100 010 001, 001, -, -, -) 태그 시스템으로의 계산 초기 단어: ba abH Hbb (halt) 순환 태그 시스템으로의 계산 초기 단어: 010 100 (=ba) 생성 규칙 단어 ---------- ------------------------------- * 010 010 010 100 (=ba) 100 010 001 10 100 001 0 100 100 010 001 - 100 100 010 001 - 00 100 010 001 - 0 100 010 001 * 010 010 100 010 001 (=abH) 100 010 001 00 010 001 010 010 001 0 010 001 010 010 - 010 001 010 010 - 10 001 010 010 - 0 001 010 010 * 010 010 001 010 010 (=Hbb) 정지의 에뮤레이트 100 010 001 01 010 010 001 1 010 010 - 010 010 001 ... ...
6행 일어나('*'가 부여되어 있다)에 순환 태그 시스템은 에뮤레이트 대상의 태그 시스템의 계산의 행에 대응하는 encode 된 내용을 생성하고 있다.이것이 정지의 에뮤레이트에 도달할 때까지 계속 된다.
참고 문헌
- Cocke, J., and Minsky, M.: "Universality of Tag Systems with P=2", J. Assoc. Comput. Mach. 11, 15-20, 1964.
- De Mol, L.: "Tag systems and Collatz-like functions", Preprint (Nr. 314), to appear in Theoretical Computer Science.
- Marvin Minsky 1961, Recursive Unsolvability of Post's Problem of "Tag" and other Topics in Theory of Turing Machines", the Annals of Mathematics, 2nd ser., Vol. 74, No. 3. (Nov., 1961), pp. 437-455. Stable URL: http://links.jstor.org/sici? sici=0003-486 X%2819611%292%3 A74%3 A3%3 C437%3 ARUOPPO%3 E2. 0. CO%3 B2-N.
- Marvin Minsky, 1967, Computation: Finite and Infinite Machines, Prentice-Hall, Inc. Englewoord Cliffs, N.J., no ISBN, Library of Congress Card Catalog number 67-12342.
- Post, E.: "Formal reductions of the combinatorial decision problem", American Journal of Mathematics, 65 (2), 197-215 (1943). (Tag systems are introduced on p.203ff.)
- Rogozhin, Yu.: "Small Universal Turing Machines", Theoret. Comput. Sci. 168, 215-240, 1996.
- Uspensky, V.A.: "A Post Machine" (in Russian), Moscow, "Nauka", 1979.
- Wang, H.: "Tag Systems and Lag Systems", Math. Annalen 152, 65-74, 1963.
외부 링크
- Tag System Wolfram MathWorld
- Cyclic Tag System Wolfram MathWorld
- C++ Simulator of a Nondeterministic and Deterministic Multitape Post Machine 프리 소프트웨어
- Bitwise Cyclic Tag (BCT) 순환 태그 시스템의 변종
This article is taken from the Japanese Wikipedia 태그 시스템
This article is distributed by cc-by-sa or GFDL license in accordance with the provisions of Wikipedia.
In addition, Tranpedia is simply not responsible for any show is only by translating the writings of foreign licenses that are compatible with CC-BY-SA license information.
0 개의 댓글:
댓글 쓰기