Product Design, Manufacturing & Innovation Resources
» 튜링 완전성

튜링 완전성

1936
  • Alan Turing
프로그래밍 언어로 튜링의 완성도를 보여주는 컴퓨터 과학 실험실.

(설명을 위한 생성된 이미지입니다)

A system of data-manipulation rules, such as a 프로그래밍 언어, is Turing complete if it can simulate any single-taped Turing machine. This means it is computationally universal and can be used to solve any computable problem, given enough time and memory. Most general-purpose programming languages are Turing complete, forming the theoretical foundation for their expressive power.

Turing completeness is a concept from computability theory that defines the power of a computational system. It originates from Alan Turing’s 1936 paper describing a theoretical device known as the Turing machine. This machine consists of an infinitely long tape, a head that can read, write, and move along the tape, and a set of states and transition rules. Despite its simplicity, a Turing machine can perform any computation that can be described algorithmically. A programming language or any other formal system is deemed ‘Turing complete’ if it has the capability to simulate a universal Turing machine. This implies that the language can compute anything that is computable.

The core requirements for a system to be Turing complete are conditional branching (e.g., if-then-else statements) and the ability to loop indefinitely or recursively (e.g., while, for loops). These constructs allow the system to make decisions and repeat operations, which is sufficient to model the behavior of a Turing machine’s state transitions and tape manipulation. The Church-Turing thesis, a fundamental principle in computer science, posits that any function that is naturally considered ‘computable’ can be computed by a Turing machine. Therefore, a Turing-complete language is, in theory, capable of expressing any algorithm.

However, this theoretical power comes with a significant consequence: the halting problem. Turing proved that it is impossible to create a general algorithm that can determine, for all possible inputs, whether any given program will finish running or continue forever. This undecidability is an inherent property of all Turing-complete systems. For this reason, some domain-specific languages are intentionally designed to be non-Turing complete. For example, standard SQL and HTML are not Turing complete, which guarantees that their scripts or definitions will terminate and prevents them from entering accidental infinite loops, a desirable property for database queries and document rendering.

UNESCO Nomenclature: 1202
컴퓨터 과학

유형

추상 시스템

분열

점진적

용법

널리 사용됨

전구체

  • Kurt Gödel’s work on incompleteness theorems
  • Alonzo Church’s development of lambda calculus
  • David Hilbert’s program to formalize mathematics
  • The concept of an algorithm dating back to antiquity

응용 프로그램

  • general-purpose programming languages (python, c++, java)
  • spreadsheet systems with macro capabilities (e.g., excel with vba)
  • minecraft’s redstone circuitry
  • cellular automata like conway’s game of life
  • some advanced sql extensions with recursive common table expressions
  • the c++ template metaprogramming subsystem
  • css3 with certain html combinations

특허:

NA

잠재적 혁신 아이디어

현재 하루 4만 건이 넘는 봇 트래픽을 차단하기 위해 이 콘텐츠는 커뮤니티 회원만 이용할 수 있습니다.
> 로그인 < 또는 >등록 < 이 콘텐츠를 비롯한 모든 제한된 콘텐츠와 도구는 (100% 무료로) 이용할 수 있습니다.

Related to: turing completeness, turing machine, computability theory, alan turing, church-turing thesis, universal computation, algorithm, formal language, decidability, halting problem.

역사적 맥락

튜링 완전성

1925
1928
1930
1936
1940
1943
1950
1924
1925
1930
1931
1939
1940
1950
1950

(날짜를 알 수 없거나 관련이 없는 경우, 예를 들어 "유체역학"의 경우, 주목할 만한 등장 시기를 대략적으로 추정하여 제공합니다.)

관련 발명, 혁신 및 기술 원칙

고화질 이미지 및 다운로드는 등록된 회원에게만 100% 무료로 제공됩니다.

> 로그인 <