언어를 튜링 완전하게 만드는 것은 무엇입니까?

A Turing tarpit 는 가능한 한 적은 수의 요소를 사용하면서 튜링 완전성을 추구하는 일종의 난해한 프로그래밍 언어입니다. Brainfuck 은 아마도 가장 잘 알려진 타핏이지만 많은 타핏이 있습니다.

• Iota 및 Jot 는 SK (I) 조합 미적분 .

• OISC ( 하나의 명령어 세트 컴퓨터 )는 일반적으로 “0보다 작거나 같은 경우 빼고 분기”하는 하나 이상의 인수에 대한 하나의 명령어 만 필요한 명령형 계산 유형을 나타냅니다. “반전 빼기 및 빌리면 건너 뛰기”. x86 MMU 는 이전 명령어를 구현하므로 Turing-complete입니다.

일반적으로 명령형 언어가 Turing-complete가 되려면 다음이 필요합니다.

1. 조건부 반복 또는 조건부 점프의 한 형태 (예 : while, if + goto)

2. 일부 형태의 저장소를 읽고 쓰는 방법 (예 : , 변수, 테이프)

lambda-calculus 기반 기능 언어가 TC가 되려면 필요 :

1. 인수에 대한 함수 추상화 기능 (예 : 람다 추상화, 인용)

2. 인수 (예 : 축소)

물론 계산을 보는 다른 방법이 있지만 이는 Turing 타 피트의 일반적인 모델입니다. 실제 컴퓨터는 무제한 저장소가 없기 때문에 범용 튜링 머신 이 아닙니다 . 엄밀히 말하면 “제한된 스토리지 시스템”입니다. 메모리를 계속 추가하면 점근 적으로 튜링 머신에 접근 할 것입니다. 그러나 제한된 저장 시스템과 유한 상태 시스템 도 계산에 유용합니다. 그들은 단순히 범용 이 아닙니다.

엄격히 말해서, I / O는 튜링 완전성을 위해 필요하지 않습니다. TC는 언어가 원하는 함수를 계산 할 수 있다고 단언하며 결과를 표시 할 수는 없습니다. 실제로 모든 유용한 언어는 어떻게 든 세상과 상호 작용하는 방법을 가지고 있습니다.

댓글

• 명령어의 경우 간단한 변수로 충분합니까? 어떤 종류의 컬렉션 (예 : 배열 또는 연결 목록)이 필요하다는 인상을 받았습니다.
• @luiscubal 임의의 양의 데이터를 지정할 수 있어야합니다. 간단한 변수를 사용하여 변수 자체에있는 데이터의 양을 나타낼 수 있습니다. N + 1 개의 서로 다른 데이터 조각을 나타내야하는 경우 어떻게해야합니까? 프랙 트란 연극과 같은 트릭 을 사용하면 간단한 변수로도 할 수 있다고 주장 할 수 있지만 … ‘ 당신이 ‘ 요구하는 내용이 아닙니다.
• ‘ 언어가 ENDLESS 루프?
• Re, ” 모든 유용한 언어는 세상과 상호 작용하는 방법을 가지고 있습니다. ” Algol 60은 세상과 상호 작용하는 정의 된 방식이 없었습니다. Algol 60 프로그램의 모든 I / O는 라이브러리 함수를 호출하여 수행되었으며 라이브러리 함수는 구현에 따라 완전히 다를 수 있습니다. 그러나 저는 Algol 60이 ” 유용한 지 여부에 대한 논의를 포기합니다. ”

더 실용적인 관점에서 볼 때 : Turing-complete 언어로 된 모든 프로그램을 자신의 언어로 번역 할 수 있다면 ( 알아요), 당신의 언어는 튜링이 완전해야합니다.따라서 디자인 한 언어가 Turing-complete인지 확인하려면 YourLanguage 컴파일러에 Brainf ***를 작성하고 모든 합법적 인 BF 프로그램을 컴파일 할 수 있음을 증명 / 시연 할 수 있습니다.

To 명확하게 말하면 YourLanguage에 대한 인터프리터 외에도 BF 프로그램을 YourLanguage로 컴파일 할 수있는 컴파일러 (모든 언어)를 작성합니다 (물론 동일한 의미를 유지).

Comments

Comments

• 예, 이것이 가장 실용적인 접근 방법입니다. </sarcasm>
• @RobertHarvey는 요점이 있지만 일반적인 아이디어는 매우 중요합니다. Brainfuck은 프로그래밍 언어가 진행됨에 따라 튜링 완전하고 매우 간단한 것으로 입증되었습니다. 난해하지 않은 프로그래밍 언어의 경우, brainfuck 인터프리터를 구현하는 것이 아무데도없이 엄격한 증거를 제공하는 것보다 훨씬 쉽고 빠를 수 있습니다 (몇 줄의 Python으로 BF를 구현할 수 있지만 저는 ‘ 파이썬이 완성되었다는 공식적인 증거로 어디서 시작해야할지 모르겠습니다. 그리고 난해한 brainfuck에서 영감을 얻은 수십 개의 언어가 완전히 튜링되는 것으로 알려져 있습니다. ‘가 brainfuck에 매핑되는 방식을 알고 있기 때문입니다.
• @RobertHarvey : 왜 안 되죠? 자신의 언어를 설계하는 사람은 BF 컴파일러를 작성할 수있을 것입니다 (필수적이라면 적절한 다른 언어를 찾을 수 있음).
• @delnan : will 그러나 귀하의 BF 인터프리터가 BF 사양을 올바르게 구현하고 있음을 증명해야합니다. IOW 귀하의 BF 인터프리터가 실제로 BF 인터프리터이며 그렇지 않을 수도있는 BF와 유사한 언어의 인터프리터가 아님을 증명해야합니다. Turing-complete.
• @ DarekNędza, ‘는 Turing Completeness가 정의 된 방식의 자연스러운 결과입니다. Turing Complete 언어의 모든 확장은 여전히 Turing Complete입니다.

시스템 만 고려할 수 있습니다. 범용 튜링 머신이 할 수있는 모든 것을 할 수 있다면 튜링이 완성되는 것입니다. 범용 튜링 머신은 주어진 시간에 계산 가능한 모든 기능을 해결할 수 있다고 알려져 있기 때문에 튜링 완성 시스템도 확장 할 수 있습니다.

튜링이 완료되었는지 확인하려면 다음을 확인하세요. 내부에 튜링 머신을 구현할 수 있습니다. 즉, 다음을 시뮬레이션 할 수 있는지 확인합니다.

1. “변수”(또는 임의 데이터)를 읽고 쓰는 기능 : 거의 자명합니다.
2. 읽기 / 쓰기 헤드 이동을 시뮬레이션하는 기능 : 변수를 검색하고 저장할 수있는 것만으로는 충분하지 않습니다. 다른 변수를 참조하기 위해 테이프의 헤드를 이동하는 기능을 시뮬레이션 할 수도 있어야합니다. 이것은 배열 데이터 구조 (또는 동등한 것)를 사용하거나 기계 코드와 같은 특정 언어의 경우 “포인터”(또는 동등한 것)를 사용하여 다른 변수를 참조하는 기능을 사용하여 프로그래밍 언어 내에서 시뮬레이션 될 수 있습니다.
3. 유한 상태 머신을 시뮬레이션하는 기능 : 자주 언급되지는 않지만 실제로 Turing 머신은 AI 개발에서 자주 사용되는 유한 상태 머신의 변형. Alan Turing은 상태의 목적은 사람의 “다양한 문제 해결 모드”를 시뮬레이션하는 것이라고 말했습니다.
4. “중단”상태 : 튜링이 완료된 것으로 간주하기 위해 일련의 규칙이 반복 될 수 있어야한다고 자주 언급되지만 어떤 식 으로든 결론을 내릴 수 없다면, 그것은 Turing이 완료되지 않았거나 알고리즘이 계산 가능한 함수가 아닌 것입니다. 작동 방식 (예 : 게임 콘솔)으로 인해 기술적으로 결론을 내릴 수없는 튜링 완성 시스템은 어떤 방식 으로든 정지 상태를 “시뮬레이션”할 수 있기 때문에이 제한을 극복 할 수 있습니다. “정지 문제”와 혼동하지 마십시오. “, 주어진 입력으로 인해 다른 시스템이 종료되지 않을 경우 100 % 신뢰성으로 감지 할 수있는 시스템을 구축하는 것이 불가능 함을 증명하는 결정 불가능한 기능입니다.

이것이 진정한 최소값입니다. 시스템이 튜링 완료로 간주되기위한 요구 사항. 그 이상도 그 이하도 아닙니다. 어떤 방식 으로든 이들 중 어떤 것도 시뮬레이션 할 수 없다면 Turing이 완료되지 않은 것입니다. 다른 사람들이 제안한 방법은 “이러한 기능이”없는 Turing 완전한 시스템이 여러 개 있기 때문에 끝까지의 수단 일뿐입니다.

진정한 Turing 완전한 시스템을 실제로 구축하는 알려진 방법은 없습니다. . 이는 물리적 공간 내에서 Turing 시스템 테이프의 무한 성을 실제로 시뮬레이션 할 수있는 알려진 방법이 없기 때문입니다.

모든 계산을 할 수 있다면 프로그래밍 언어가 완성 된 것입니다.”언어 튜링을 완성하는 기능 집합이 하나만있는 것이 아니므로 루프가 필요하거나 변수가 필요하다는 답변이 잘못되었습니다. 둘 다없는 a 언어가 있기 때문입니다. >하지만 튜링이 완성되었습니다.

Alan Turing은 범용 튜링 머신을 만들었으며 범용 머신에서 작동하도록 설계된 프로그램을 사용자의 언어로 실행되도록 번역 할 수 있다면 튜링도 완성되었습니다. 이것은 또한 간접적으로 작동하므로 모든 범용 튜링 머신 프로그램이 Y 프로그램으로 번역 될 수 있으므로 튜링 완성 언어 Y에 대한 모든 프로그램이 X로 번역 될 수 있다면 언어 X가 튜링 완료라고 말할 수 있습니다.

시간 복잡성 , 공간 복잡성, 입력 / 출력 형식의 용이성 및 프로그램 작성의 용이성은 방정식에 포함되어 있지 않으므로 이러한 기계는 전력 손실로 인해 계산이 중단되지 않거나 지구가 태양에 삼켜지는 경우 이론적으로 모든 계산을 수행 할 수 있습니다.

보통 튜링 완성도를 증명하기 위해 튜링 완성 된 언어로 입증 된 모든 언어에 대한 통역사를 만들지 만 작동하려면 입력 및 출력 수단이 필요합니다. 언어가 튜링 완성을 위해 실제로 필요하지 않은 두 가지입니다. 프로그램이 시작시 상태를 변경할 수 있고 프로그램이 중지 된 후 메모리를 검사 할 수 있으면 충분합니다.

성공적인 언어를 만들려면 완성도를 높이는 것 이상이 필요합니다. 튜링 타 피트에도 적용됩니다. BrainFuck 이 , 및 ..

댓글

• ” 모든 계산을 수행 할 수 있다면 프로그래밍 언어가 완성됩니다. ” 그 ‘는 Church-Turing 논문이지 언어를 Turing- 완전하게 만드는 것이 아닙니다.
• @Rhymoid 그럼 통역사를 만들 수 없으면 튜링이 완성되지 않는다는 뜻입니까? 즉, 람다 미적분은 튜링이 같더라도 튜링이 완료되지 않습니다 ‘?
• ‘ Turing-equivalent 및 Turing-complete (및 Turing-powerful) 용어에 대한 권위있는 정의를 찾고 있습니다. I ‘ 게시판에있는 사람들부터 자신의 논문에서이 용어를 다르게 해석하는 ‘ 연구자에 이르기까지 이미 너무 많은 사례를 보았습니다.
• 어쨌든, 저는 ‘ 튜링 완료 ‘를 Universal Turing Machine (UTM; 그러면 모든 Turing 머신을 시뮬레이션 할 수 있습니다. 따라서 ‘ 범용 ‘). 1936 년의 Turing ‘ 논문에서 그는 자신의 기계를 소개하고 UTM의 개념을 정의하고 UTM이 Church와 동일한 시뮬레이션이라는 증거를 스케치했습니다. ‘의 람다 계산법. 그렇게함으로써 그는 그들이 동일한 계산 능력을 가지고 있음을 증명했습니다. Church-Turing 논문은 간단히 말해서 ” ‘가 모든 컴퓨팅 능력을 ‘ 계속 “.
• 위키 백과의 튜링 완성 페이지에 대한 두 가지 공식적인 정의가 있습니다. . 하나는 I / O가 필요하고 다른 하나는 I / O가 필요하지 않습니다. ‘ ‘ 모든 Turing 계산 가능 함수를 계산할 수 있다면 기계가 튜링 완료라고 말하지 않는 것입니다. 모든 튜링 머신 프로그램과 동일하게 계산하는 람다 미적분에서 동등한 프로그램을 쉽게 만들 수 있기 때문에 람다 미적분을 튜링 완료로 되돌립니다.

무제한 반복 또는 중지 여부를 “알 수 없습니다.

————-

설명 : 어떤 입력이 주어지면 모든 경우에 (다른 튜링 머신을 사용하여) 그 사물이 무한 반복 될 것인지 아니면 결국 멈출 것인지를 알 수는 없습니다. 멈 춥니 다.하지만 반복되는 경우는 아닙니다!).

이것은 어떤 방식 으로든 잠재적으로 무제한의 데이터를 저장할 수 있어야 함을 의미합니다. 아무리 그렇더라도 무한 테이프에 해당하는 것이 있어야합니다. 복잡합니다. 일반적으로 튜링 머신은 제어 가능한 수단으로 상태의 크기를 늘리거나 줄일 수 있습니다.

튜링의 원래 범용 튜링 머신에는 해결할 수없는 중지 문제가 있기 때문에 자신의 튜링 전체 머신에도 해결할 수없는 중지가 있어야합니다. 문제.

튜링 완성 시스템은 다른 모든 튜링 완성 시스템을 에뮬레이트 할 수 있으므로 시스템에서 잘 알려진 튜링 완성 시스템에 대한 에뮬레이터를 구축 할 수 있다면 시스템도 튜링 완성이라는 것을 증명할 수 있습니다.

예를 들어 Snakes & 사다리가 무한히 반복되는 격자 패턴이있는 보드 (위에 다른 버전이있는 왼쪽). 2- 카운터 Minsky 머신이 Turing 완료 (무제한 카운터 2 개와 유한 수 중 1 개 상태 포함)라는 사실을 알면 그리드의 X 및 Y 위치가 2 개 카운터의 현재 값인 동등한 보드를 구성 할 수 있습니다. 현재 경로는 현재 상태입니다. 쾅! 스네이크 & 사다리가 튜링 완료되었음을 방금 증명했습니다.

댓글

• 나는 ‘ 그 인수를 사지 마십시오. 튜링 머신에서 중지 문제를 결정할 수 없다고해서 중지 문제를 결정할 수없는 프로그램을 지정할 수있는 모든 표기법이 튜링이 완료되었음을 직접 의미하지는 않습니다. 그 반대 만이 분명합니다. 표기법이 Turing complete이면 물론 중단 문제를 결정할 수없는 프로그램을 작성할 수 있습니다.
• It ‘ 필요한 조건입니다. 모든 프로그램에 대해 중지 여부를 결정할 수 있다면 언어는 ‘ 튜링이 완료되지 않은 것입니다.

한 가지 필수 조건은 반복 이전에 결정되지 않은 최대 반복 횟수가있는 루프 또는 최대 재귀 깊이가 미리 결정되지 않은 반복입니다. 예를 들어, 많은 최신 언어에서 찾을 수있는 for … in … 루프는 언어 튜링을 완성하기에 충분하지 않습니다 (하지만 다른 방법이 있습니다). 이것은 제한된 수의 반복 또는 제한된 재귀 깊이를 의미하는 것이 아니라 최대 반복 및 재귀 깊이를 미리 계산해야 함을 의미합니다.

예를 들어 Ackermann 함수는 다음이없는 언어에서 계산 될 수 없습니다. 반면에, 이러한 기능 없이도 매우 복잡하고 유용한 소프트웨어를 많이 작성할 수 있습니다.

반면에 모든 반복 횟수와 모든 재귀 깊이를 미리 계산할뿐만 아니라 프로그램 중단 여부를 결정할 수 있지만 정지 합니다.

나는 이것이 공식적으로 정답이 아니라는 것을 알고 있지만, “튜링 완료”에서 “최소”를 선택하고 “실용”을 원래 위치로 되 돌리면 프로그래밍 언어를 구별하는 가장 중요한 기능을 볼 수 있습니다. 마크 업 언어는

• 변수
• 조건 (if / then …)
• loopage (loop / break, while …)

다음 com e

• 익명 및 명명 된 함수

이러한 주장을 테스트하려면 HTML과 같은 마크 업 언어로 시작하십시오. 변수 만 사용하거나 조건부 만 사용하는 HTML + (MS는 조건부 주석으로 처리 함) 또는 일종의 루프 구조 (조건부 없이는 <repeat n="4">...</repeat>). 이러한 작업을 수행하면 HTML +가 일반 HTML보다 훨씬 더 강력 해지지 만 (?) 여전히 프로그래밍 언어보다는 마크 업에 가깝습니다. 각각의 새로운 기능을 사용하면 선언적이지 않고 명령형 언어가됩니다.

논리와 프로그래밍의 최소화에 대한 탐구는 확실히 중요하고 흥미 롭습니다. 그러나 제가 어린 나이나 노인들에게 “프로그래밍이란 무엇인가”와 “프로그래밍을 배우는 방법”을 가르쳐야한다면 거의 시작하지 않을 것입니다. 튜링 완성도의 이론적 기초의 전체 폭과 폭으로. 요리와 프로그래밍의 모든 본질은 올바른 순서로 일을하고 엄마가했던 것처럼 준비 될 때까지 반복하는 것입니다. / p>

다시 CS를 완료하지 못했습니다.

댓글

• 확실하지 않으면 먼저 조사해야합니다. fractran 은 튜링 완료 이며 brainf * ck . 또한 html 5 + CSS 3 는 rule 110 .
• yesyesyes 그렇습니다.하지만 주어진 모든 예는 다소 난해합니다 (흥미 롭거나 놀랍지 만), m y 대답은 실용적인 대답이었고 아마도 전혀 최소한이 아닐 것입니다. ‘이 점을 지적하는 것이 중요하다고 생각합니다.이 페이지는 Google에서 Turing-completeness를 검색 할 때 1 위였으며 여기에 대한 답변은 n00bie에게 거의 사용되지 않는 IMHO입니다. HTML과 PHP 또는 Python의 차이점을 알고 싶어하는 사람. 내 말은, brainf ck는 아무 이유없이 brainf ck라고 부르지 않습니다.