Turing Complete

Why Trust Techopedia

What is Turing Complete?

Turing complete refers to the ability of a system or programming language to solve any problem that can be solved by a Turing machine – a theoretical mathematical model invented by mathematician Alan Turing in 1936. Turing completeness denotes the capability to carry out any calculation feasible on a general-purpose computer.

Advertisements

In theoretical computer science, Turing complete is a foundational concept that describes many technologies and systems prevalent today. It extends from modern programming languages like Python to artificial intelligence (AI), particularly in the areas of machine learning (ML) and deep learning. In AI, the concept of Turing completeness reflects the ability of AI systems to perform complex computations and solve a wide range of problems.

Essentially, Turing complete defines a system that possesses the capacity to navigate through complex computations, depending on sufficient resources such as time and memory. Turing completeness is not limited to technology systems. Its principles can be applied more broadly to any system that can simulate a Turing machine.

Techopedia Explains the Turing Complete Meaning

    The Turing machine itself is a hypothetical machine composed of three theoretical components: a limited set of states, an infinite amount of storage, and a transition function. With these attributes, the Turing machine represents certain boundaries of traditional computation.

    A simple representation of a Turing machine consists of the following:

    Tape
    A tape that is split into cells, one beside the other. Every cell includes a symbol from a certain finite alphabet. The alphabet includes a unique blank symbol as well as one or more other symbols. The volume of tape required for the computation is always included in the Turing machine.

    Head
    A head that is able to write and read symbols on the tape. In certain models, the head moves while the tape is fixed.

    State register
    A state register to store the Turing machine’s state. There is a special start state through which the state register is initialized.
    Finite table
    A finite table (sometimes referred to as a transition function or an action table) of instructions, which are generally quintuples, but occasionally quadruples.

    University of Cambridge
    Source: University of Cambridge

    Despite its simplicity, a Turing machine can be tailored to replicate the logic associated with any computer algorithm. With this in mind, many modern programming languages are said to be Turing complete, meaning they can emulate the same computing principles noted in Turing’s theory. However, a technicality applies – because none of these systems have an infinite amount of storage or run for infinite time. Turing completeness is assessed on what the rules allow for, rather than practical limitations.

    The idea of Turing completeness is useful in modern computer theory, but completely separate from the Turing Test, which is Turing’s idea of assessing whether technologies can simulate human intelligence effectively.

    History of Turing Complete

    The first Turing-complete machine would have been Charles Babbage’s analytical engine (1830s) had it been built at the time it was designed. The analytical engine was a proposed digital mechanical general-purpose computer, incorporating an arithmetic logic unit, control flow in the form of conditional branching and loops, and integrated memory.

    The first computer that was Turing complete in practice was the ENIAC in 1946.

    How to Determine Turing Completeness?

    In theory, any language or system that can perform the operations required by a Turing machine can be considered Turing complete. The most common way to determine Turing completeness is to evaluate if the system or programming language has the necessary features to simulate a Turing machine (i.e., create a Turing machine emulator with it).

    Importance in Computing

    Turing completeness serves as a universal standard for evaluating the computational power of systems and programming languages, playing a significant role in shaping the theory and practice of computing.

    From language design to system architecture and software engineering, Turing completeness influences various aspects of computing. In software development, for example, it serves as a key influencer in design decisions, algorithm development, and language selection.

    Examples of Turing Complete Systems

    Cryptocurrency: Ethereum

    Ethereum is an example of a Turing complete blockchain – its scripting language, Solidity, is Turing complete. This enables developers to write decentralized applications and intricate smart contracts with complex logic and functionality.

    In contrast, Bitcoin is considered Turning incomplete. Bitcoin’s scripting language is intentionally limited in its capabilities to ensure security and prevent potential vulnerabilities.

    Programs: Spreadsheets

    Microsoft Excel, as introduced in the 1980s, was Turing incomplete. Excel supported only scalar values and did not allow for user-defined functions.

    In December 2020, Microsoft announced the LAMBDA function in Excel – a function to create other functions – making the Excel formula language Turing-complete.

    Similar spreadsheet programs, like Google Sheets and Apache OpenOffice Calc are also considered Turing complete when combined with their respective scripting languages – Google Apps Script and OpenOffice Basic.

    Turing Complete Pros and Cons

    Pros

    • Can solve a wide range of computational problems
    • Create complex algorithms and applications
    • Provides a common standard for evaluating computational capabilities.

    Cons

    • Complex code may inadvertently contain vulnerabilities
    • Increased complexity can lead to higher costs
    • Requires significant computational resources

    The Bottom Line

    By definition, Turing complete refers to the ability of a system or language to solve any problem that can be solved by a Turing machine – essentially having the capacity to navigate complex computations, depending on sufficient resources such as time and memory.

    However, this complexity comes at a cost. While Turing complete systems offer more functionality, they also involve increased complexity and potential security risks, as the likelihood of introducing vulnerabilities is higher.

    FAQs

    What is Turing Complete in simple terms?

    Is Minecraft Turing complete?

    Is DNA Turing complete?

    What is the Turing complete rule?

    Advertisements

    Related Questions

    Related Terms

    Vangie Beal
    Technology Expert
    Vangie Beal
    Technology Expert

    Vangie Beal is a digital literacy instructor based in Nova Scotia, Canada, who has recently joined Techopedia. She’s an award-winning business and technology writer with 20 years of experience in the technology and web publishing industry.  Since the late ’90s, her byline has appeared in dozens of publications, including CIO, Webopedia, Computerworld, InternetNews, Small Business Computing, and many other tech and business publications.  She is an avid gamer with deep roots in the female gaming community and a former Internet TV gaming host and games journalist.