튜링 완전이란 무엇입니까?
https://stackoverflow.com/questions/7284
-
08-06-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian문제
"튜링 컴플리트(Turing Complete)"라는 표현은 무엇을 의미하나요?
너무 많은 이론적 세부 사항을 다루지 않고 간단한 설명을 해주실 수 있습니까?
해결책
가장 간단한 설명은 다음과 같습니다.
Turing Complete 시스템은 답을 찾을 수 있는 프로그램을 작성할 수 있는 시스템을 의미합니다(런타임이나 메모리에 대한 보장은 없지만).
따라서 누군가가 "나의 새로운 것은 Turing Complete입니다"라고 말한다면 이는 원칙적으로(비록 실제로는 아니지만) 모든 계산 문제를 해결하는 데 사용될 수 있음을 의미합니다.
가끔 장난이겠지...한 사람이 vi로 Turing Machine 시뮬레이터를 작성했으므로 vi가 세상에서 필요한 유일한 계산 엔진이라고 말할 수 있습니다.
다른 팁
가장 간단한 설명은 다음과 같습니다.
앨런 튜링(Alan Turing)은 프로그램을 가져와 해당 프로그램을 실행하고 결과를 표시할 수 있는 기계를 만들었습니다.하지만 그는 다양한 프로그램을 위해 다양한 기계를 만들어야 했습니다.그래서 그는 어떤 프로그램이라도 가져와서 실행할 수 있는 "범용 튜링 머신"을 만들었습니다.
프로그래밍 언어는 해당 기계와 유사합니다(가상이지만).그들은 프로그램을 가져와서 실행합니다.이제, 충분한 시간과 메모리가 주어지면 Turing 기계가 실행할 수 있는 모든 프로그램(언어에 관계없이)을 실행할 수 있는 프로그래밍 언어를 "Turing Complete"라고 합니다.
예를 들어:10개의 숫자를 가져와서 더하는 프로그램이 있다고 가정해 보겠습니다.튜링 기계는 이 프로그램을 쉽게 실행할 수 있습니다.하지만 이제 어떤 이유로 인해 프로그래밍 언어가 동일한 추가 작업을 수행할 수 없고 Turing 기계가 불완전하다고 상상해 보세요.반면에 범용 튜링 기계처럼 어떤 프로그램이든 실행할 수 있다면 튜링 완료입니다.
Java, JavaScript, Perl 등과 같은 대부분의 최신 프로그래밍 언어는 덧셈, 곱셈, if-else 조건, 반환 문, 데이터 저장/검색/삭제 방법 등과 같은 프로그램을 실행하는 데 필요한 모든 기능을 모두 구현하기 때문에 모두 튜링 완전합니다. .
업데이트:내 블로그 게시물에서 자세히 알아볼 수 있습니다. "JavaScript는 Turing Complete입니다" — 설명됨
에서 위키피디아:
앨런 튜링 (Alan Turing)의 이름을 따서 명명 된 튜링 완전성은 지금까지 컴퓨팅 장치를위한 모든 그럴듯한 디자인이 보편적 인 튜링 기계에 의해 모방 될 수 있다는 점에서 중요하다.따라서 보편적 인 튜링 머신 역할을 할 수있는 기계는 원칙적으로 다른 프로그래밍 가능한 컴퓨터가 가능하다는 계산을 수행 할 수 있습니다.그러나 이것은 기계에 대한 프로그램을 작성하는 데 필요한 노력, 기계가 계산을 수행하는 데 걸리는 시간, 또는 기계가 계산과 관련이없는 능력과 관련이 없습니다.
진정한 튜링-완성 기계는 물리적으로 불가능할 가능성이 높지만, 무제한 보관이 필요하기 때문에 튜링 완전성은 종종 무제한 스토리지가있는 경우 보편적 인 물리적 기계 나 프로그래밍 언어에 기인합니다.모든 현대 컴퓨터는 이런 의미에서 튜링에 완료됩니다.
"튜링 완료는 '충분한 시간과 공간이 주어지면 계산 가능한 문제에 답할 수 있다'는 것을 의미합니다"라고 말하는 것 외에는 어떻게 그보다 더 비기술적일 수 있는지 모르겠습니다.
비공식적 정의
튜링 완전 언어는 모든 계산을 수행할 수 있는 언어입니다.그만큼 교회-튜링 논제 수행 가능한 모든 계산은 Turing 기계에 의해 수행될 수 있다고 명시합니다.ㅏ 튜링 머신 무한한 랜덤 액세스 메모리와 해당 메모리를 읽고, 쓰고, 이동해야 하는 시기, 특정 결과로 종료되어야 하는 시기, 다음에 수행할 작업을 지시하는 유한한 '프로그램'을 갖춘 기계입니다.튜링 기계에 대한 입력은 시작되기 전에 메모리에 저장됩니다.
튜링이 아닌 언어를 완전하게 만들 수 있는 것들
튜링 기계는 메모리에서 본 내용을 기반으로 결정을 내릴 수 있습니다. - 오직 지원하는 '언어' +, -, *, 그리고 / 정수에 대한 입력은 입력을 기반으로 선택할 수 없기 때문에 Turing 완전하지 않지만 Turing 기계는 가능합니다.
튜링 기계는 영원히 작동할 수 있다 - Java, Javascript 또는 Python을 사용하여 모든 종류의 루프, GOTO 또는 함수 호출을 수행하는 기능을 제거하면 결코 끝나지 않는 임의의 계산을 수행할 수 없기 때문에 Turing Complete가 아닙니다. 콕 종료되지 않는 프로그램을 표현할 수 없는 정리 증명자이므로 Turing Complete가 아닙니다.
튜링 기계는 무한한 메모리를 사용할 수 있습니다 - Java와 똑같지만 4GB 이상의 메모리를 사용하면 종료되는 언어는 Turing 완전체가 아닙니다. Turing 기계는 무한한 메모리를 사용할 수 있기 때문입니다.이것이 우리가 실제로 할 수 없는 이유입니다. 짓다 Turing 기계이지만 Java는 여전히 Turing 완전한 언어입니다. 언어 무한한 메모리를 사용하는 것을 방지하는 제한이 없습니다.이것이 정규식이 Turing 완전하지 않은 이유 중 하나입니다.
튜링 머신에는 랜덤 액세스 메모리가 있습니다 - 기억을 통해서만 작업할 수 있는 언어 push 그리고 pop 스택에 대한 작업은 Turing 완료가 아닙니다.문자열을 읽는 '언어'가 있다면 한 번 스택에서 푸시 및 팝을 통해서만 메모리를 사용할 수 있습니다. ( 문자열에는 자체가 있습니다 ) 나중에 보면 밀어서 ( 그리고 보면 터진다 ).그러나 모든 경우에 대해 알려줄 수는 없습니다. ( 자신의 것이있다 ) 나중에 그리고 모든 [ 자신의 것이있다 ] 나중에 (주의하세요. ([)] 이 기준을 충족하지만 ([]] 하지 않습니다).튜링 머신은 랜덤 액세스 메모리를 사용하여 추적할 수 있습니다. ()'모래 []는 별도로 있지만 스택만 있는 이 언어는 그럴 수 없습니다.
Turing 기계는 다른 Turing 기계를 시뮬레이션할 수 있습니다. - 적절한 '프로그램'이 주어지면 튜링 기계는 다른 튜링 기계의 '프로그램'을 가져와 임의의 입력에 대해 시뮬레이션할 수 있습니다.Python 인터프리터 구현이 금지된 언어가 있다면 Turing Complete가 아닐 것입니다.
튜링 완전 언어의 예
귀하의 언어에 무한 랜덤 액세스 메모리, 조건부 실행 및 어떤 형태의 반복 실행이 있다면 아마도 Turing Complete일 것입니다.Turing 기계가 할 수 있는 모든 것을 여전히 달성할 수 있는 더 이국적인 시스템이 있으며, 이로 인해 Turing도 완전해집니다.
- 유형이 지정되지 않은 람다 미적분학
- 콘웨이의 인생 게임
- C++ 템플릿
- 프롤로그
기본적으로 튜링 완전성은 하나의 간결한 요구 사항, 무제한 재귀입니다.
기억에 얽매이지도 않습니다.
독립적으로 생각했지만, 여기에 몇 가지 토론이 있습니다 주장의. LSP에 대한 나의 정의 더 많은 맥락을 제공합니다.
여기의 다른 답변은 Turing-completeness의 기본 본질을 직접 정의하지 않습니다.
가장 간단한 용어로 Turing-complete 시스템은 가능한 모든 계산 문제를 해결할 수 있습니다.
주요 요구 사항 중 하나는 스크래치 패드 크기에 제한이 없으며 스크래치 패드에 대한 이전 쓰기에 액세스하기 위해 되감기가 가능하다는 것입니다.
따라서 실제로는 어떤 시스템도 Turing-complete가 아닙니다.
오히려 일부 시스템은 무한한 메모리를 모델링하고 시스템 메모리 내에 들어갈 수 있는 모든 가능한 계산을 수행하여 튜링 완전성을 근사합니다.
내 생각에 "Turing Complete" 개념의 중요성은 프로세스를 더 단순하고 간단한 명령으로 구성된 "간단한" 명령으로 분해할 수 있는 컴퓨팅 기계(기계적/전기적 "컴퓨터"일 필요는 없음)를 식별하는 능력에 있다고 생각합니다. Universal Machine이 해석하고 실행할 수 있는 명령입니다.
주석이 달린 튜링(The Annotated Turing)을 적극 추천합니다.
@Mark 내 생각에 당신이 설명하는 내용은 Universal Turing Machine과 Turing Complete에 대한 설명이 혼합된 것 같습니다.
실용적인 의미에서 Turing Complete란 프로그램으로 작성되고 표현될 수 있으며 Universal Machine(데스크탑 컴퓨터)에 의해 실행될 수 있는 기계/프로세스/계산입니다.다른 사람들이 언급했듯이 시간이나 저장 공간을 고려하지는 않습니다.
내가 이해하는 간단한 단어는 다음과 같습니다.
튜링 컴플리트 : 계산을 할 수 있는 프로그래밍 언어/프로그램은 Turing Complete입니다.
예를 들어 :
Just를 사용하여 두 개의 숫자를 추가할 수 있나요? HTML.(안은 '아니요', 덧셈을 하려면 자바스크립트를 사용해야 합니다.) 따라서 HTML은 Turing Complete가 아닙니다.
Java, C++, Python, Javascript, Solidity for Ethereum 등과 같은 언어는 Turing Complete입니다. 이 언어를 사용하면 두 숫자를 더하는 것과 같은 계산을 할 수 있기 때문입니다.
도움이 되었기를 바랍니다.
처럼 웨일런 플린이 말했다.:
Turing Complete는 최소한 Turing Machine만큼 강력하다는 것을 의미합니다.
나는 이것이 틀렸다고 생각합니다. 시스템이 Turing Machine만큼 강력하다면 시스템은 Turing Complete입니다.기계가 수행하는 모든 계산은 시스템이 수행할 수 있지만 시스템이 수행하는 모든 계산은 튜링 기계가 수행할 수도 있습니다.
대부분의 프로그래머에게 친숙한 실용적인 언어 용어로, Turing 완전성을 감지하는 일반적인 방법은 언어가 중첩된 무한 while 문의 시뮬레이션을 허용하는지 여부입니다(고정된 상한이 있는 파스칼 스타일 for 문과 반대).
관계형 데이터베이스가 장소와 도로의 위도와 경도를 입력하고 이들 사이의 최단 경로를 계산할 수 있습니까?이는 SQL이 튜링 완전하지 않음을 보여주는 문제 중 하나입니다.
하지만 C++에서는 그렇게 할 수 있고 어떤 문제라도 해결할 수 있습니다.그렇습니다.
