“완료”라는 표현은 무엇을 의미합니까?
너무 많은 이론적 세부 사항을 보지 않고 간단한 설명을 해 줄 수 있습니까?
답변
가장 간단한 설명은 다음과 같습니다.
튜링 컴플리트 (Touring Complete) 시스템은 응답을 찾을 수있는 프로그램을 작성할 수있는 시스템을 의미합니다 (런타임 또는 메모리에 대한 보장은 없지만).
따라서 누군가가 “실제로 자주는 아니지만”원칙적으로 “내 새로운 것은 Turing Complete”라고 말하면 계산 문제를 해결하는 데 사용될 수 있습니다.
언젠가는 농담입니다. 한 남자가 vi에서 튜링 머신 시뮬레이터를 썼기 때문에 vi가 세계에서 유일하게 필요한 계산 엔진이라고 말할 수 있습니다.
답변
가장 간단한 설명은 다음과 같습니다
Alan Turing은 프로그램을 작성하고 해당 프로그램을 실행하며 결과를 보여줄 수있는 머신을 만들었습니다. 그러나 그는 프로그램마다 다른 기계를 만들어야했습니다. 그래서 그는 모든 프로그램을 가지고 실행할 수있는 “Universal Turing Machine”을 만들었습니다.
프로그래밍 언어는 가상 머신이지만 해당 머신과 유사합니다. 그들은 프로그램을 가지고 실행합니다. 이제 충분한 시간과 메모리가 주어진 튜링 머신이 실행할 수있는 프로그램 (언어에 관계없이)을 실행할 수 있다면 이제 프로그래밍 언어를 “완료 중”이라고합니다.
예를 들어 : 10 개의 숫자를 받아서 더하는 프로그램이 있다고 가정 해 봅시다. 튜링 머신은이 프로그램을 쉽게 실행할 수 있습니다. 그러나 어떤 이유로 든 프로그래밍 언어가 동일한 추가 기능을 수행 할 수 없다고 상상해보십시오. 이것은 “불완전한 투어”(말하자면)입니다. 반면, 범용 Turing 머신이 실행할 수있는 프로그램을 실행할 수 있으면 Turing이 완료된 것입니다.
대부분의 최신 프로그래밍 언어 (예 : Java, JavaScript, Perl 등)는 추가, 곱셈, if-else 조건, return 문, 저장 / 검색 / 삭제 방법과 같은 프로그램을 실행하는 데 필요한 모든 기능을 각각 구현하기 때문에 튜링 완료입니다. 데이터 등.
업데이트 : 내 블로그 게시물 “자바 스크립트가 완료되었습니다” 에 대한 자세한 내용을 볼 수 있습니다 — 설명
답변
에서 위키 피 디아 :
Alan Turing의 이름을 딴 튜링 완성도는 지금까지 진보 된 컴퓨팅 장치를위한 모든 그럴듯한 디자인이 보편적 인 튜링 머신에 의해 모방 될 수 있다는 점에서 중요합니다. 따라서, 범용 튜링 기계의 역할을 할 수있는 기계는 원칙적으로 다른 프로그램 가능한 컴퓨터가 할 수있는 모든 계산을 수행 할 수 있습니다. 그러나 이것은 기계에 대한 프로그램을 작성하는 데 필요한 노력, 기계가 계산을 수행하는 데 걸리는 시간 또는 기계와 관련이없는 기계가 가질 수있는 능력과는 아무런 관련이 없습니다.
진정한 Turing-complete 머신은 물리적으로 불가능할 수 있지만 무제한 스토리지가 필요하기 때문에 Turing 완성도는 스토리지가 무제한 인 경우 보편적 인 물리적 머신 또는 프로그래밍 언어로 인해 느슨하게 나타납니다. 이 점에서 모든 최신 컴퓨터는 튜링이 완료되었습니다.
“완전한 의미는 ‘충분한 시간과 공간이 주어지면 계산 가능한 문제에 대답 할 수있다”는 말을 제외하고는 기술보다 비 기술적 인 방법을 모릅니다.
답변
비공식적 정의
튜링 완성 언어는 모든 계산을 수행 할 수있는 언어입니다. 교회 튜링의 논문의 모든 수행 가능한 계산은 튜링 기계에 의해 수행 될 수있는 상태. 튜링 기계는 무한 랜덤 액세스 메모리와 유한 ‘프로그램’을 가진 기계가 지시는, 그것이 어떤 결과를 종료해야하는 메모리에서 쓰기 및 이동, 그리고 무엇 다음에 무엇을해야을 읽어야합니다. 튜링 머신으로의 입력은 시작하기 전에 메모리에 저장됩니다.
튜링되지 않은 언어를 만들 수있는 것들
튜링 기계는 메모리에 보는 것을 기반으로 의사 결정을 내릴 수 만 지원이 있다는 ‘언어’- +, -, *, 그리고 /그것의 입력에 따라 선택을 할 수 없기 때문에 정수에 완료 튜링되지 않습니다,하지만 튜링 기계가 있습니다.
Turing 머신은 영원히 실행될 수 있습니다. Java, Javascript 또는 Python을 가져 와서 루프, GOTO 또는 함수 호출을 수행하는 기능을 제거하면 임의의 계산을 수행 할 수 없으므로 Turing이 완료되지 않습니다. 결코 끝나지 않습니다. Coq 는 종료되지 않는 프로그램을 표현할 수없는 정리 증명 자이므로 Turing이 완료되지 않았습니다.
튜링 머신은 무한 메모리를 사용할 수 있습니다. 튜링 머신은 무한 메모리를 사용할 수 있기 때문에 정확히 자바와 같지만 4 기가 바이트 이상의 메모리를 사용한 후에는 종료되는 튜링 시스템이 아닙니다. 우리가 실제로 할 수없는 이유입니다 구축 튜링 기계를하지만, 자바 때문에 자바는 여전히 튜링 완전한 언어 언어는 무한한 메모리를 사용을 방지에는 제한이 없습니다. 이것이 정규 표현식이 튜링이 완료되지 않은 이유입니다.
튜링 기계는 랜덤 액세스 메모리가 – 단지 당신을 통해 메모리에서 작동 할 수있는 언어 push와 pop스택에 작업이 완료 튜링되지 않습니다. 문자열을 한 번 읽고 스택에서 밀고 터지는 방식으로 만 메모리를 사용할 수 있는 ‘언어’가 (있는 경우 문자열을 )볼 (때 튀어 나올 때 밀면 나중에 문자열 자체가 있는지 여부를 알 수 있습니다 ). 모든이 경우, 그것은 나를 말할 수없는 (자신의가 )에 이상이 와 모든이 [그것의 자신의 ](주 나중에 ([)]이 기준을 충족하지만, ([]]하지 않습니다). 튜링 기계 추적하기 위해 랜덤 액세스 메모리를 사용할 수 ()의 및[]별도이지만 스택 만있는이 언어는 사용할 수 없습니다.
튜링 머신은 다른 튜링 머신을 시뮬레이션 할 수 있습니다. 튜링 머신은 적절한 ‘프로그램’이 주어지면 다른 튜링 머신의 ‘프로그램’을 가져와 임의의 입력에서 시뮬레이션 할 수 있습니다. 파이썬 인터프리터를 구현할 수없는 언어가 있다면 튜링이 완벽하지 않을 것입니다.
튜링 언어의 예
언어에 무한 랜덤 액세스 메모리, 조건부 실행 및 반복 된 실행 형식이 있으면 튜링이 완료된 것일 수 있습니다. 튜링 머신이 할 수있는 모든 것을 여전히 달성 할 수있는 더 이국적인 시스템이 있습니다.
- 형식화되지 않은 람다 미적분
- 콘웨이의 인생 게임
- C ++ 템플릿
- 프롤로그
답변
기본적으로 Turing-completeness는 무한한 재귀라는 하나의 간결한 요구 사항입니다.
메모리에 묶여 있지도 않습니다.
나는 이것을 독립적으로 생각했지만 여기 에 주장에 대한 토론 이 있습니다. LSP에 대한 나의 정의 는 더 많은 맥락을 제공합니다.
다른 답변은 Turing-completeness의 기본 본질을 직접 정의하지는 않습니다.
답변
튜링 컴플리트는 튜링 머신 만큼 강력하다는 것을 의미합니다 . 이는 Turing Machine으로 계산할 수있는 모든 것이 Turing Complete 시스템으로 계산 될 수 있음을 의미합니다.
아무도 튜링 머신보다 강력한 시스템을 아직 찾지 못했습니다. 따라서 당분간 시스템이 튜링 컴플리트라고 말하는 것은 시스템이 알려진 컴퓨팅 시스템만큼 강력하다고 말하는 것과 같습니다 ( 교회 순회 논문 참조 ).
답변
가장 간단한 용어로 Turing-complete 시스템은 가능한 모든 계산 문제를 해결할 수 있습니다.
주요 요구 사항 중 하나는 스크래치 패드 크기에 제한이 없으며 이전 스크래치 패드 쓰기에 액세스하기 위해 되 감을 수 있습니다.
따라서 실제로 어떤 시스템도 Turing-complete가 아닙니다.
오히려 일부 시스템은 무한 메모리를 모델링하고 시스템 메모리에 맞는 가능한 계산을 수행하여 Turing-completeness에 근접합니다.
