열거자(컴퓨터 과학)

이 기사는 대부분 또는 전체적으로 단일 출처에 의존하고 있습니다. 관련 토론은 토크 페이지에서 확인할 수 있습니다. 추가 출처에 인용문을 도입하여 이 기사의 개선에 도움을 주시기 바랍니다.출처 : 'Enumerator' 컴퓨터 사이언스– 뉴스 · 신문 · 서적 · 학자 · JSTOR ( 2021년 5월)

열거기는 프린터가 연결된 튜링 기계입니다.튜링 기계는 그 프린터를 문자열을 인쇄하는 출력 장치로 사용할 수 있다.튜링 머신은 목록에 문자열을 추가할 때마다 프린터로 문자열을 보냅니다.열거자는 튜링 기계의 한 종류이며 튜링 기계와 동등합니다.

형식적 정의

이 섹션은 어떠한 출처도 인용하지 않습니다. 신뢰할 수 있는 출처에 인용문을 추가하여 이 섹션의 개선에 도움을 주십시오. 소스되지 않은 소재는 이의를 제기하여 삭제할 수 있습니다. (2021년 4월) (이 템플릿메시지를 삭제하는 방법과 타이밍에 대해 설명합니다)

$열거자{\displaystyle }$E({$displaystyle$ E$})$는 언어가 ${{displaystyle \emptyset$인 2소켓 튜링 머신($여기$서 k ${\displaystyle =}$ {$displaystyle$ k$=2$으로 정의할 수 있습니다. 처음에 E$({displaystyle$ E$})$는 입력되지 않으며 모든 테이프는 공백으로 채워집니다.새로 정의된 기호${\displaystyle \mathrm{}}$#${\displaystyle \mathrm{\gamma }}$ #$$ #${\displaystyle \mathrm{display}}$ display display$display$ σ {\ display 、 \ \ \ $Gamma \land$ \ # \ $notin \ Sigma$$\}$는$$S $요소$의 끝을 나타내는 딜리미터입니다.두 번째 테이프는 프린터로 간주되며 문자열은$\#{\displaystyle \mathrm{}}$ $display$ $style \$$$# 로 구분됩니다$.$$열거자{\displaystyle }$E$(\$$displaystyle$ E$)$에 의해 열거된 L$displaystyle$ L$(E))$로 $나타나는{\displaystyle }$ 언어는 두 번째 테이프(프린터)의 문자열 세트로 정의됩니다.

열거자와 튜링 기계의 동등성

유한 알파벳 위의 언어는 열거자에 의해 열거될 수 있는 경우에만 튜링 인식 가능합니다.이것은 튜링 인식 가능한 언어도 재귀적으로 열거할 수 있다는 것을 보여준다.

증명

튜링 인식 가능 언어는 열거자에 의해 열거될 수 있습니다.

튜링 $머신{\displaystyle }$M({$display style$ M$})$에서 받아들일 수 있는 언어는 L$)$ {$display style L($입니다.입력 알파벳$\sigma {\displaystyle \mathrm{}}$(\$displaystyle \Sigma$}, 즉$$ Kleen Closure $\sigma {\displaystyle {\mathrm{}}^{}}${ { ${\displaystyle {\{}^{}}$ { { 、 \$displaystyle$ \$Sigma ^*}$ }} is$$ is is is is is is is is is,,,,,,,,,,,,,,,,,,,,,,,, the the the the the the,,,,,,,,,${\displaystyle {s\mathrm{}}_{}}$1, ${\displaystyle {}_{}{2\mathrm{}}_{}}$,${\displaystyle \dots ,}$ ${\displaystyle s_{}}$ i$,$ {\$displaystyle s_{1$}, $s_{2},\displays, s_{i}$ 등$$그런 다음 L${\displaystyle (}$ ${\displaystyle M}$) {$displaystyle$ L$(M)}$ $언어$를 열거하는 열거자가 다음 단계를 따릅니다.

i = 1, 2, 3,... 2 입력 $문자열{\displaystyle {}_{}}$ ${\displaystyle {s\mathrm{}}_{}}$1, ${\displaystyle {}_{}{2\mathrm{}}_{}}$,${\displaystyle \dots ,}$ ${\displaystyle s_{}}$i {\$displaystyle$ $s_{1$}, $s_{2$$},\displaystyle$$s_{$$i$}를 $사용$하여 M {$displaystyle$ M$}$을 실행합니다.3단계 허용되는 문자열이 있으면 인쇄합니다.  

Now the question comes whether every string in the language ${\displaystyle L(M)}$ will be printed by the Enumerator we constructed.언어 L$)$의 문자열$$ w(\$displaystyle L($M$))$에 $대해{\displaystyle }$ TM$M$(\$displaystyle$M)은$$ 이를 받아들이기 위해 제한된 수의 스텝을 실행합니다$(\displaystyle$w의$$ $경우{\displaystyle }$ k$(\$$displaystyle$ k$)).$그런 다음 Enumerator $\displaystyle$ w$\$displaystyle k$\$에 인쇄됩니다.따라서 Enumerator는$$M {\$displaystyle$ M$}$이 인식하는 모든 $문자열$을 인쇄하지만 단일 문자열을 여러 번 인쇄할 수 있습니다.

열거 가능한 언어는 튜링 인식 가능

열거형 $L$을 인식하는 Turing $Machine{\displaystyle }$M$($$디스플레이$ 스타일 $M$을 구축하는 것은 매우 간단합니다.테이프 2개를 가질 수 있습니다.한 테이프에서는 입력 문자열을 사용하고 다른 테이프에서는 열거자를 실행하여 언어의 문자열을 차례로 열거합니다.두 번째 테이프에 문자열이 인쇄되면 첫 번째 테이프에 입력된 문자열과 비교합니다.일치하는 경우 입력을 받아들이고 그렇지 않으면 거부합니다.

레퍼런스

Sipser, Michael (2012). Introduction to the Theory of Computation - International Edition. ISBN 978-1-133-18781-3.