태그 시스템
Tag system태그 시스템은 1943년 에밀 레온 포스트가 포스트 표준 시스템의 단순한 형태로 출판한 결정론적 계산 모델이다.태그 시스템은 포스트 태그 머신이라고 불리는 추상적인 기계로도 볼 수 있다(Post-Turing 기계와 혼동되지 않음). 즉, 테이프가 무한 길이의 FIFO 대기열인 유한 상태 기계로서, 기계가 각 전환마다 큐의 머리에서 기호를 읽으면 머리에서 일정한 수의 기호를 삭제한다.그리고 이 전환에서 읽은 첫 번째 기호에 전적으로 의존하는 기호 문자열을 꼬리 부분에 추가한다.
표시된 모든 작업은 한 번의 전환으로 수행되기 때문에 태그 기계는 한 가지 상태만 엄격하게 가지고 있다.
정의들
태그 시스템은 트리플트(m, A, P)이며,
- m은 삭제 번호라 불리는 양의 정수다.
- A는 기호의 유한한 알파벳으로, 그 중 하나는 특수한 정지 기호다.A의 모든 유한한(아마도 비어 있을 것 같은) 현을 낱말이라고 한다.
- P는 생산 규칙의 집합으로, A의 각 기호 x에 P(x)(생산이라고 함)를 할당한다.정지 기호에 할당된 생산(예: P(H))은 연산에는 아무런 역할을 하지 않지만 편의를 위해 P(H) = 'H'로 간주된다.
중지 단어란 중지 기호로 시작하거나 길이가 m보다 작은 단어를 말한다.
변환 t(태그 연산이라 함)는 비할링 단어 집합에서 정의되는데, 만약 x가 S 단어의 가장 왼쪽 기호를 가리킨다면 t(S)는 S의 가장 왼쪽 m 기호를 삭제하고 오른쪽에 P(x)라는 단어를 추가한 결과다.따라서 이 시스템은 m-심볼 헤드를 가변 길이의 꼬리로 처리하지만 생성된 꼬리는 전적으로 머리의 첫 번째 기호에 의존한다.
태그 시스템에 의한 계산은 변환 t를 반복함으로써 생성되는 단어의 유한한 시퀀스로, 처음에는 주어진 단어로 시작해서 중단단어가 생성될 때 정지한다.(이 정의에 따르면, 중단 단어가 정밀하게 많은 반복으로 생성되지 않는 한, 연산은 존재하지 않는 것으로 간주된다.대체 정의는 예를 들어 출력을 인코딩하는 단어를 식별하기 위해 알파벳의 특별한 하위 집합을 사용하여 비할당 계산을 허용한다.)
m-태그 시스템이라는 용어는 종종 삭제 번호를 강조하기 위해 사용된다.정의는 문헌(cf Reference)에 다소 차이가 있는데, 여기에서 제시된 것은 로고진(Rogozhin)의 정의다.
위의 정의에서 정지 기호를 사용하면 계산의 출력이 최종 단어로만 인코딩되는 반면, 그렇지 않으면 출력물은 태그 연산을 반복하여 생성된 단어의 전체 순서에 인코딩된다.
일반적인 대체 정의는 정지 기호를 사용하지 않으며 m보다 작은 길이의 모든 단어를 정지 단어로 처리한다.또 다른 정의는 Post 1943(아래 역사적 노트에 설명되어 있음)이 사용한 원래의 정의로, 여기서 중지되는 유일한 단어는 빈 문자열이다.
예:간단한 2-태그 일러스트
이것은 단지 정지 기호를 사용하는 단순한 2-태그 시스템을 설명하기 위한 것이다.
2-태그 시스템 알파벳: {a,b,c,H} 생산 규칙: a --> ccbaH b --> ccca c --> cc 연산 초기 단어:baacca cccbaHcca Hcccccccccccccccca(halt). 예제: Collatz 시퀀스 계산
이 간단한 2-태그 시스템은 [De Mol, 2008]에서 채택되었다.정지 기호는 사용하지 않지만, 길이가 2보다 작은 단어에 정지하며, 약간 수정된 버전의 콜라츠 시퀀스를 계산한다.
원래의 Collatz 시퀀스에서 n의 후계자는 다음 중 하나이다.n/2 (짝수 n) 또는 3n + 1 (홀수 n)3n + 1 값은 홀수 n에 대해 분명히 짝수이므로 3n + 1 이후의 다음 용어는 확실히 3n + 1/2이다.아래 태그 시스템에 의해 계산된 순서에서 우리는 이 중간 단계를 생략하고, 따라서 n의 후속은 홀수 n의 경우 3n + 1/2이다.
이 태그 시스템에서 양의 정수 n은 a가 n인 aa...a라는 단어로 표현된다.
2-tag 시스템 알파벳:{a,b,c}생산 규칙:-->bcb,>c,>aaa 계수 초기 단어:aaa<-->n=3 abc cbc caaaaaaaa<--5aaabc. ABcbccbccaaaaaaaaaaaaa<--> 8 aaaaaabcaaabcaaabc aabcbc aabcbcbcbcbcbcbca bcbca bcaaaa aaa <--> 4 aabcBCBC bca aa <--> 2 bc a <--> 1(iii) m-태그 시스템의 튜링-완전성
각 m > 1에 대해, m 태그 시스템의 세트는 튜링 완성이다. 즉, 각 m > 1에 대해, 주어진 튜링 머신 T에 대해, T를 에뮬레이션하는 m 태그 시스템이 있는 경우다.특히, 왕 1963년과 코크 & 민스키 1964년처럼 유니버설 튜링 기계를 모방하기 위해 2-태그 시스템을 구축할 수 있다.
반대로 튜링 기계는 튜링-완전 등급의 m-태그 시스템을 모방할 수 있다는 것을 증명함으로써 범용 튜링 기계임을 보여줄 수 있다.예를 들어, 로고진 1996은 알파벳 {a1, ..., an, H}과 그에 상응하는 프로덕션 {aaWnn1, ..., aaWnnn-1, aaW, aaann, H}과 함께 2태그 시스템 클래스의 보편성을 증명했는데, 여기서 W는k 비어 있지 않은 단어였다. 그리고 나서 그는 매우 작은(4주, 6심볼)의 보편성을 증명했다.이러한 종류의 태그 시스템을 시뮬레이션할 수 있다는 것을 보여줌으로써 튜링 머신.
2-태그 중지 문제
이 중단 문제의 버전은 가장 간단하고 가장 쉽게 설명되는 불변의 결정 문제들 중 하나이다.
임의의 양의 정수 n과 알파벳 {1,2,...,n}에 있는 n+1 임의 단어 P1,P2,...,Pn,Q의 목록이 주어지면 태그 연산 t: ijX → XP는i 결국 Q를 2 미만의 단어로 변환하는가?즉, 순서 Q, t1(Q), t2(Q), t(Q), ...가3 종료되는가?
태그 시스템의 정의에 대한 기록 참고 사항
위의 정의는 태그 시스템이 정지 기호를 사용하지 않고 오히려 빈 단어에서만 정지하며 태그 연산은 다음과 같이 정의되는 포스트 1943의 정의와 다르다.
- x가 비어 있지 않은 단어 S의 가장 왼쪽 기호를 나타내는 경우, t(S)는 먼저 단어 P(x)를 S의 오른쪽 끝에 추가한 다음 결과의 가장 왼쪽 m 기호를 삭제하여 m 기호보다 작은 경우 모두 삭제하는 작업이다.
m > 1에 대한 m-태그 시스템 세트의 튜링-완전성에 관한 위의 언급은 Post에서 원래 정의한 이러한 태그 시스템에도 적용된다.
이름 "태그"의 기원
1943년 포스트의 각주에 따르면, B. P. Gill은 첫 번째 m 기호가 그대로 남아 있는 문제의 이전 변종의 이름을 제안했지만, 오히려 매 단계마다 m 기호에 의해 현재 위치가 오른쪽으로 이동한다는 것을 나타내는 체크 표시를 제안했다.이어 체크 마크가 시퀀스 끝에 닿는지 여부를 판단하는 문제의 명칭을 아이들의 태그 놀이를 가리키며 '태그의 문제'로 명명했다.
주기 태그 시스템
순환 태그 시스템은 원래 태그 시스템의 수정이다.알파벳은 0과 1이라는 두 개의 기호로만 구성되어 있으며, 제작 규칙은 순차적으로 고려되는 제작 목록으로 구성되며, 리스트의 "마지막" 제작을 검토한 후 목록 시작 부분으로 되돌아간다.각 생산에 대해 단어의 가장 왼쪽 기호를 검사한다. 기호가 1이면 현재 생산물이 단어의 오른쪽 끝에 추가된다. 기호가 0이면 단어에 어떤 문자도 추가되지 않는다. 어느 경우든 가장 왼쪽 기호는 삭제된다.이 시스템은 단어가 비게 되면 중단된다.
예
주기율 태그 시스템 프로덕션: (010, 000, 1111) 연산 초기 단어: 11001 생산 워드 -------------------------------------------- 11001 000 10010 1111 001010000 010 01010000 000 101000000 11 010000000 010 10000000 . . . .
순환 태그 시스템은 매튜 쿡에 의해 만들어졌고 규칙 110 세포 자동화가 보편적이라는 쿡의 시연에서 사용되었다.시범의 핵심 부분은 주기 태그 시스템이 튜링-완전한 태그 시스템의 클래스를 모방할 수 있다는 것이었다.
주기적 태그 시스템에 의한 태그 시스템 에뮬레이션
알파벳 {a1, ..., an} 및 해당 프로덕션 {P1, ..., Pn}이(가) 있는 m-태그 시스템은 m*n 프로덕션(Q1, ..., Qn, -, -, -, -)을 포함한 주기태그 시스템에 의해 에뮬레이션되며, 여기서 첫 번째 n 프로덕션을 제외한 모든 제품은 빈 문자열('-'로 표시됨)이다.Q는k 태그 시스템 알파벳의 각 기호를 다음과 같이 길이-n 이진 문자열로 교체하여 얻은 각k P의 인코딩이다(이들은 태그 시스템 계산의 초기 단어에도 적용된다).
a1 = 100...00 a2 = 010...00... an = 000...01
즉, a는k 왼쪽에서 k 위치에th 1이 있는 이진 문자열로 인코딩되며, 0은 다른 곳에 있다.태그 시스템 계산의 연속 선은 주기적 태그 시스템에 의해 에뮬레이션의 모든 (m*n)th 선으로 인코딩된다.
예
이것은 에뮬레이션 기법을 설명하기 위한 아주 작은 예다.
2-tag system Production rules: (a --> bb, b --> abH, H --> H) Alphabet encoding: a = 100, b = 010, H = 001 Production encodings: (bb = 010 010, abH = 100 010 001, H = 001) Cyclic tag system Productions: (010 010, 100 010 001, 001, -, -, -) Tag system computation Initial word: ba abHHbb (halt) 순환 태그 시스템 계산 초기 단어: 010 100 (=ba) 생산 워드 --------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- 010 001 100 010 001 100 100 001 010 001 010 001 - 100 010 001 - 001 - 001 - 001 - 0010 100 010 001 * 010 010 100 010 001 00 010 001 00 010 001 010 001 010 001 010 010 010 010 010 - 010 001 010 010 - 10 001 010 010 - 010 010 010 010 - 010 010 010 010 - 010 010 010 010 * 010 010 010 010 010 010 010 010 010 010 010 010 010 010 010 010 010 * 010 010 010 010 010 010 010 010 010 010ted stop --> 001 010 010 010 (=Hbb) 100 010 001 01 010 010 01 010 1 010 010 - 010 010 001 ……
주기적 태그 시스템에 의해 생성된 6번째 라인('*'로 표시됨)은 에뮬레이트된 정지에 도달할 때까지 태그 시스템 계산의 해당 라인의 인코딩이다.
참고 항목
참조
- Cocke, John; Minsky, Marvin (1964). "Universality of Tag Systems with P=2". J. Assoc. Comput. Mach. 11: 15–20. doi:10.1145/321203.321206.
- De Mol, Liesbeth (January 2008). "Tag systems and Collatz-like functions". Theoretical Computer Science. 390 (1): 92–101. doi:10.1016/j.tcs.2007.10.020. hdl:1854/LU-436211.
- 마빈 민스키 1961, "태그"와 기타 튜링 머신 이론의 포스트 문제의 재귀 불능성, 수학 연보, 2학년, 74번, 3번 (1961년 11월), 페이지 437–455. JSTOR 1970290.
- Minsky, Marvin (1967). Computation: Finite and Infinite Machines. Englewoord Cliffs, N.J.: Prentice–Hall, Inc. pp. 267–273. LCCN 67-12342.
- 14장 "계산성에 대한 매우 간단한 기초"에서, 민스키는 14.6항 매우 읽기 쉬운 (그리고 심사된) 하위섹션을 제시한다."태그"와 모노제닉 캐논 시스템(pp. 267–273)의 문제(이 하위 섹션은 "태그 시스템"으로 색인화된다).민스키는 "포스트는 이 (00, 1101) 문제가 "난해할 수 없다"고 느꼈고, 나 또한 컴퓨터의 도움을 받아도 그랬다"는 그의 좌절감을 일반적인 문제와 연관시킨다.그는 "S로 시작했을 때 이 과정이 반복될 것인지 여부를 어떤 문자열 S에 대해서도 효과적으로 결정할 수 있는 방법"이라고 언급하지만, 몇 가지 구체적인 사례가 확인되지는 않았다.특히 그는 코크의 정리 및 코롤라리 1964년에 대해 언급한다.
- Post, E.: "합병 의사결정 문제의 공식적 감소", American Journal of Mathics, 65(2), 197–215(1943).(태그 시스템은 페이지 203ff에 도입된다.)
- 로고진, 유. : "작은 범용 튜링 머신", 정리. 계산하다. 168, 215–240, 1996.
- 왕, H.: "태그 시스템과 라그 시스템", 수학. 안날렌 152, 65–74, 1963.
