언어의 "튜링 완전성"을 평가하기 위한 실제 지침은 무엇입니까?

https://stackoverflow.com/questions/449014

19-08-2019
|

문제

나는 읽었다 "튜링 완료란 무엇인가" 그리고 Wikipedia 페이지도 있지만 저는 공식적인 증명보다는 Turing Complete가 된다는 실제적인 의미에 더 관심이 있습니다.

제가 실제로 결정하려고 하는 것은 제가 방금 디자인한 장난감 언어가 범용 언어로 사용될 수 있는지 여부입니다.나는 그것을 사용하여 Turing 기계를 작성할 수 있다면 그것을 증명할 수 있다는 것을 알고 있습니다.그러나 나는 성공이 확실할 때까지 그 연습을 하고 싶지 않습니다.

Turing Completeness가 없으면 불가능한 최소한의 기능 세트가 있습니까?완전성을 사실상 보장하는 기능 세트가 있습니까?

(제 생각에는 조건부 분기와 읽기/쓰기 가능한 메모리 저장소가 대부분의 방법을 제공할 것입니다.)

편집하다:

"Turing Complete"라고 말하면서 방향을 틀었다고 생각합니다.나는 특정 기능 세트를 갖춘 새로 발명된 언어(또는 특정 명령어 세트가 있는 VM)가 컴퓨팅 가치가 있는 모든 것을 계산할 수 있을 것이라는 합리적인 확신을 갖고 추측하려고 노력하고 있습니다.나는 그것을 사용하여 Turing 기계를 만들 수 있다는 것을 증명하는 것이 한 가지 방법이지만 유일한 방법은 아니라는 것을 알고 있습니다.

내가 기대했던 것은 다음과 같은 일련의 지침이었습니다."X, Y, Z를 할 수 있다면 아마 뭐든지 해."

해결책

동적 할당 구조의 형태가 필요합니다 (malloc 또는new 또는 cons 재귀 함수 또는 무한 루프를 작성하는 다른 방법. 당신이 그것들을 가지고 있고 전혀 흥미로운 일을 할 수 있다면, 당신은 거의 확실히 튜링을 완료합니다.

Lambda 미적분학은 튜링 머신의 전원이 동일하며 Lambda 미적분학을 구현하면 실제로 Lambda 미적분학 프로그램을 작성하는 것은 매우 재미 있습니다. 방법 튜링 머신을위한 프로그램을 작성하는 것보다 더 재미 있습니다!

제가 알고있는 튜링-완성의 유일한 실질적인 의미는 종료되지 않는 프로그램을 작성할 수 있다는 것입니다. 나는 종료를 보장하는 몇 가지 특수 목적 언어를 사용 했으므로 ~ 아니다 튜링-완성. 때로는 보장 된 종료 대가로 추가 표현력을 포기하는 것이 유용합니다.

다른 팁

'완전성' 임의의 표현을 표현할 수있는 속성을 설명합니다. 알고리즘 계산, 그것이 요점이었습니다 튜링의 기계 처음에. 언어 또는 논리 시스템은이 속성이있는 경우 'Turing Complete'로 설명 할 수 있습니다. 실용적인 관점에서 볼 때 모든 범용 프로그래밍 언어와 놀랍게도 많은 특수 목적 언어는 적절하게 느슨한 정의를 위해이를 수행 할 수 있습니다 (아래 참조).

그러나 튜링 완전성에 대한 엄격한 정의는 물리적으로 불가능한 무한한 저장 용량을 의미합니다. 이를 감안할 때, 물리적 기계는 완전 할 수는 없지만,이 제약은 프로그래밍 언어에 대한 완전성을 완성 할 때 일반적으로 (적어도 비공식적으로) 편안합니다. 언어에 대한 튜링 완전성에 대한 사소한 테스트 중 하나는 언어가 튜링 머신 시뮬레이터를 구현하는 데 사용될 수 있는지 여부입니다.

완전하지 않은 광범위한 시스템의 예는 Codd의 논문에 설명 된 SQL의 이론적 근거 인 관계 적 대수입니다. 대규모 공유 데이터 은행의 관계형 모델. 관계 대수는의 재산을 가지고 있습니다 고델 완전성, 이는 다음과 같이 정의 할 수있는 계산을 표현할 수 있음을 의미합니다. 1 차 술어 미적분학 (즉, 일반적인 논리적 표현). 그러나 임의의 알고리즘 계산을 표현할 수 없기 때문에 튜링에 완료되지 않습니다.

모든 실용적인 SQL 방언이 대부분의 모든 실용적인 SQL 방언이 절차 적 구성으로 순수한 관계형 모델을 프로그래밍 언어에 일반적으로 적용되는 정의에 의해 완료되는 정도까지 순수한 관계형 모델을 확장하는 것은 아닙니다. 그러나 개별 SQL 쿼리는 전반적으로는 아닙니다.

Turing 완전한 도메인 별 언어의 더 심각한 예는 다음과 같습니다. 텍사스 그리고 sendmail.cf,. 후자의 경우 실제로 sendmail.cf를 사용하는 사람의 유명한 예가 있습니다. 범용 튜링 머신 시뮬레이터를 구현하십시오.

당신이 쓸 수 있다면 Brainf $ &# 당신의 언어로 통역사, 그것은 turing-complete입니다. lolcode 정확히 이런 식으로 튜링에 완전한 것으로 판명되었습니다.

튜링이 불완전하지 않은 언어의 예는 자주 가지고 있습니다 경계 루프, 처럼:

for i=1 to N {...}

그러나 부족합니다 무한한 보다 일반적인 조건을 확인하는 루프는 다음과 같습니다.

while bool_expr {...}

가능한 모든 루핑 구조물이 제한되면 프로그램이 종료되도록 보장됩니다. 그리고 무조건 종료 보증이 잠재적으로 유용하지만 언어가 촉진되지 않는다는 것을 나타냅니다.

또한 못을 박습니다 가능합니다 루핑 구조물은 어려울 수 있습니다. 예를 들어, 나는 C ++ 템플릿이 Turing-complete를 의도하지 않았다고 확신합니다 ...

"최소 기능 세트"가 있는지 확실하지 않지만 언어가 완전하고 있음을 증명하기 위해서는 다른 튜링 완전 시스템 (반드시 튜링 머신이 아님)을 모방 할 수 있음을 증명하면됩니다. 다른 시스템은 튜링을 완료하는 것으로 알려져 있습니다. http://en.wikipedia.org/wiki/turing_complete#examples Turing Complete Systems의 전체 목록이 있습니다. 그들 중 일부는 튜링 머신보다 간단합니다.

Norman Ramsey가 말한 것에 대해 한 가지 경고를 추가하고 싶습니다. 튜링 머신에는 무한한 메모리가 있으므로 완전한 것으로 간주되는 프로그래밍 언어는 메모리도 무한하다는 가정하에 있습니다.

Brainfuck은 튜링을 완료하고 루프 구조와 메모리 증분/감소 만 가지고 있으므로 충분합니다.

반면에 Lambda 미적분학에서 값을 수정할 방법은 없지만 완전한 값이 완료되므로 변경 가능한 메모리없이 수행 할 수 있습니다.

아마도 당신의 프로그램은 Lambda 미적분학과 아무 관련이 없을 가능성이 높습니다. 실질적인 답변을 위해서는 최소값은 다음과 같습니다.

변수에 쓰는 방법
변수를 읽는 방법
조건부 GOTO의 형태 (IF 문, 루프 등)

나는 다음과 같은 것을 본 기억이 없다 최소 기능 튜링 완전성을 위해.그러나 귀하의 언어가 루프와 조건부 분기를 지원한다면 Turing Complete일 가능성이 높습니다.그러나 이를 증명할 수 있는 유일한 방법은 여전히 Turing Machine이나 다른 Turing Complete 언어를 시뮬레이션하는 것입니다.

Turing 기계를 구현할 수 있다면(구현 가능한 한, 무제한 메모리를 갖춘 수학적 구조이기 때문에[테이프 크기는 무한함]) Turing이 완전하다고 확신할 수 있습니다.

몇 가지 징후:

메모리를 확인하고 현재 값을 기반으로 조작할 수 있을 뿐만 아니라 이를 사용하여 프로그램 흐름을 제어할 수도 있습니다.
해당 메모리는 할당된 메모리, 추가할 수 있는 문자열, 재귀를 통해 메모리를 할당할 수 있는 스택 등이 될 수 있습니다.
프로그램 흐름은 반복 또는 선택 기반 재귀를 통해 이루어질 수 있습니다.

비 종료 가능성이있는 모든 언어는 거의 완전합니다. 무한 루핑 구조 (루프 또는 다시 도달 할 수있는 goto와 같은)를 제공함으로써 언어가 아닌 언어를 만들거나 일반적인 재귀를 제공함으로써 (제한없이 함수를 호출하도록함으로써) 언어를 만들 수 있습니다.

일단 당신 ~이다 Turing Complete, 당신은 당신의 자신을 포함한 다른 Turing 완전한 언어를 해석하는 것과 같은 일을 할 수 있습니다.

진짜 질문은 "무엇이 좋은가요?"입니다. 특정 도메인에서 특정 문제를 해결하기 위해 언어를 사용하는 경우, 완전하지 않은 언어로 솔루션을 표현하는 것이 더 나을 수 있습니다.

X가 비 링 완전 언어로 제공되는 다른 튜링 완전 언어에서 "이것, 또는 무엇이든 X가 제공 한 결과와 함께"작성하여 항상 튜링 완전성을 추가 할 수 있습니다.

물론, 하나의 언어 만 사용하고 싶다면 아마도 완전한 튜링을하는 것이 더 나았을 것입니다 ...

당신은 에뮬레이션을 시도 할 수 있습니다 OISC (하나의 명령 세트 컴퓨터). 지침 중 하나를 모방 할 수 있다면, 그 단일 지침을 사용하여 튜링 완전한 기계를 작성할 수 있으므로 언어도 완전한 튜팅을해야한다는 것을 증명했습니다.

튜링 완전성이 불가능한 최소 기능 세트가 있습니까? 실제로 완전성을 보장하는 일련의 기능이 있습니까?

예, 데이터에 대한 조건부의 흐름이 필요합니다. 종종 표현되는 것 if. 예를 들어 a +-*/ 조건부를 표현할 수있는 방법이 없기 때문에 포켓 계산기는 튜링에 완료되지 않습니다.

또한 프로그램의 초기 지점으로 다시 점프 할 수 있어야하며, 그 위에 루프를 구현할 수 있습니다. 예를 들어, 프로그램이 종료 될 것을 보장하기 위해 뒤로 점프를 금지하는 BPF도 완료되지 않습니다.

읽을 수 있고 쓰기 쉽고 임의로 큰 스토리지가 필요합니다. 예를 들어, 두 개의 32 비트 변수 만있는 언어는 계산할 수있는 내용이 제한됩니다. 포인터, 어레이, 스택, 단점, 순수한 데이터 구조 등으로 주소 지정된 메모리 (메모리).

이 외에도 다른 모든 프로그래밍 언어를 구축 할 수 있습니다. 쉽지 않거나 빠르지는 않지만 충분합니다.

... 튜링의 실질적인 영향보다는 완전한 의미보다.

나는 튜링을 완료한다는 실질적인 의미가 의심 스럽다.

Turing Complete Machines (예 : 원본)의 일부 예를 보면 튜링 머신, 당신은 실제 계산에 유용하지 않다는 것을 알 수 있습니다.

라이센스 : CC-BY-SA ~와 함께 속성

제휴하지 않습니다 StackOverflow