Turing Complete 란 무엇입니까?
"완료"라는 표현은 무엇을 의미합니까?
너무 많은 이론적 세부 사항을 보지 않고 간단한 설명을 해 줄 수 있습니까?
가장 간단한 설명은 다음과 같습니다.
Turing 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이 완전하지 않습니다.
Turing 머신은 무한 메모리를 사용할 수 있습니다. Java와 정확히 동일하지만 4 기가 바이트 이상의 메모리를 사용한 후에는 종료되는 언어는 Turing 머신이 무한 메모리를 사용할 수 있기 때문에 완료되지 않습니다. 우리가 실제로 할 수없는 이유입니다 구축 튜링 기계를하지만, 자바 때문에 자바는 여전히 튜링 완전한 언어 언어는 무한한 메모리를 사용을 방지에는 제한이 없습니다. 이것이 정규 표현식이 튜링이 완료되지 않은 이유입니다.
튜링 기계는 랜덤 액세스 메모리가 - 단지 당신을 통해 메모리에서 작동 할 수있는 언어 push와 pop스택에 작업이 완료 튜링되지 않습니다. 문자열을 한 번 읽고 스택에서 밀어서 튀어 나와서 메모리 만 사용할 수 있는 '언어'가 (있는 경우 문자열을 )볼 (때 튀어 나올 때 밀면 나중에 문자열 자체가 있는지 여부를 알 수 있습니다 ). 모든이 경우, 그것은 나를 말할 수없는 (자신의가 )에 이상이 와 모든이 [그것의 자신의 ](주 나중에 ([)]이 기준을 충족하지만, ([]]하지 않습니다). 튜링 기계 추적하기 위해 랜덤 액세스 메모리를 사용할 수 ()의 및[]별도이지만 스택 만있는이 언어는 사용할 수 없습니다.
튜링 머신은 다른 튜링 머신을 시뮬레이션 할 수 있습니다. 튜링 머신은 적절한 '프로그램'이 주어지면 다른 튜링 머신의 '프로그램'을 가져와 임의의 입력에서 시뮬레이션 할 수 있습니다. 파이썬 인터프리터를 구현할 수없는 언어가 있다면 튜링이 완벽하지 않을 것입니다.
튜링 언어의 예
언어에 무한 랜덤 액세스 메모리, 조건부 실행 및 반복 된 실행 형식이 있으면 튜링이 완료된 것일 수 있습니다. 튜링 머신이 할 수있는 모든 것을 여전히 달성 할 수있는 더 이국적인 시스템이 있습니다.
- 형식화되지 않은 람다 미적분
- 콘웨이의 인생 게임
- C ++ 템플릿
- 프롤로그
기본적으로 Turing-completeness는 간결한 요구 사항 중 하나이며 무한한 재귀입니다.
메모리에 묶여 있지도 않습니다.
나는 이것을 독립적으로 생각했지만 여기 에 주장에 대한 토론 이 있습니다. LSP에 대한 나의 정의 는 더 많은 맥락을 제공합니다.
다른 답변은 Turing-completeness의 기본 본질을 직접 정의하지는 않습니다.
튜링 컴플리트는 튜링 머신 만큼 강력하다는 것을 의미합니다 . 이는 Turing Machine에서 계산할 수있는 모든 항목이 Turing Complete 시스템에서 계산 될 수 있음을 의미합니다.
아무도 튜링 머신보다 강력한 시스템을 아직 찾지 못했습니다. 따라서 당분간 시스템이 튜링 컴플리트라고 말하는 것은 시스템이 알려진 컴퓨팅 시스템만큼 강력하다고 말하는 것과 같습니다 ( 교회 순회 논문 참조 ).
가장 간단한 용어로 Turing-complete 시스템은 가능한 모든 계산 문제를 해결할 수 있습니다.
주요 요구 사항 중 하나는 스크래치 패드 크기에 제한이 없으며 이전 스크래치 패드 쓰기에 액세스하기 위해 되 감을 수 있습니다.
따라서 실제로 어떤 시스템도 Turing-complete가 아닙니다.
오히려 일부 시스템은 무한 메모리를 모델링하고 시스템 메모리에 맞는 가능한 계산을 수행하여 튜링 완성도에 근접합니다.
"Turing Complete"라는 개념의 중요성은 프로세스를보다 간단하고 간단한 "간단한"명령어로 분해 할 수있는 컴퓨팅 머신 (기계적 / 전기적 "컴퓨터"일 필요는 없음)을 식별하는 능력에 있다고 생각합니다. Universal 머신이 해석하고 실행할 수있는 명령.
저는 Annotated Turing을 강력히 추천합니다
@ Mark 나는 당신이 설명하는 것이 Universal Turing Machine에 대한 설명과 Turing Complete의 혼합이라고 생각합니다.
실제로 Turing Complete는 Universal Machine (데스크톱 컴퓨터)에 의해 실행되는 프로그램으로 작성되고 표현 될 수있는 머신 / 프로세스 / 계산 일 것입니다. 다른 사람들이 언급했듯이 시간이나 저장을 고려하지는 않습니다.
간단한 단어로 이해하는 것 :
Turing Complete : 계산을 수행 할 수있는 프로그래밍 언어 / 프로그램은 Turing complete입니다.
예를 들면 다음과 같습니다.
당신은 그냥 사용하여 두 개의 번호를 추가 할 수 HTML을 . (Ans는 ' No '이므로 자바 스크립트를 사용하여 추가해야합니다.) 따라서 HTML은 Turing Complete가 아닙니다.
Java, C ++, Python, Javascript, Ethereum 용 Solidity 등과 같은 언어는 Turing Complete입니다.이 언어를 사용하여 두 개의 숫자를 추가하는 것과 같은 계산을 수행 할 수 있기 때문입니다.
도움이 되었기를 바랍니다.
튜링 완료는 튜링 머신만큼 강력하다는 것을 의미합니다.
나는 이것이 틀렸다고 생각한다. Turing Machine만큼 강력하다면 시스템은 Turing complete이다. 즉, 기계에 의해 수행되는 모든 계산은 시스템에 의해 수행 될 수 있지만 시스템에 의해 수행 된 모든 계산은 Turing 기계에 의해 수행 될 수있다 .
대부분의 프로그래머에게 친숙한 실제 언어 용어에서 Turing 완성도를 감지하는 일반적인 방법은 언어가 중첩 된 무한 명령문의 시뮬레이션을 허용하거나 허용하는지 여부입니다 (고정 된 상한을 갖는 명령문의 파스칼 스타일과 반대).
관계형 데이터베이스가 위도와 경도의 장소와 도로를 입력하고 그 사이의 최단 경로를 계산할 수 있습니까? 이것은 SQL이 Turing complete가 아님을 나타내는 한 가지 문제입니다.
그러나 C ++로 할 수 있으며 문제가 발생할 수 있습니다. 따라서입니다.
참고 URL : https://stackoverflow.com/questions/7284/what-is-turing-complete
'development' 카테고리의 다른 글
| 데이터베이스에 비밀번호를 저장하는 가장 좋은 방법 (0) | 2020.02.17 |
|---|---|
| 배경 이미지에 CSS 필터를 적용하는 방법 (0) | 2020.02.17 |
| 파일의 특정 줄에 대한 커밋 로그를 검색 하시겠습니까? (0) | 2020.02.16 |
| Ruby에서 include와 require의 차이점은 무엇입니까? (0) | 2020.02.16 |
| N 번 반복 된 단일 항목 목록 만들기 (0) | 2020.02.16 |