What is Turing Complete

Question

What does the expression  Turing Complete  mean    Can you give a simple explanation  without going into too many theoretical details

User · Answer

Super-brief summary from what Professor Brasilford explains in this video.

Turing Complete ? do anything that a Turing Machine can do.

It has conditional branching (i.e. "if statement"). Also, implies "go to" and thus permitting loop.
It has arbitrary amount of memory (e.g. long enough tape) that the program needs.

User · Answer

From wikipedia      Turing completeness  named after Alan   Turing  is significant in that every   plausible design for a computing   device so far advanced can be emulated   by a universal Turing machine     an   observation that has become known as   the Church-Turing thesis  Thus  a   machine that can act as a universal   Turing machine can  in principle    perform any calculation that any other   programmable computer is capable of    However  this has nothing to do with   the effort required to write a program   for the machine  the time it may take   for the machine to perform the   calculation  or any abilities the   machine may possess that are unrelated   to computation       While truly Turing-complete machines   are very likely physically impossible    as they require unlimited storage    Turing completeness is often loosely   attributed to physical machines or   programming languages that would be   universal if they had unlimited   storage  All modern computers are   Turing-complete in this sense    I don t know how you can be more non-technical than that except by saying  turing complete means  able to answer computable problem given enough time and space

User · Answer

In practical language terms familiar to most programmers  the usual way to detect Turing completeness is if the language allows or allows the simulation of nested unbounded while statements  as opposed to Pascal-style for statements  with fixed upper bounds

User · Answer

Turing Complete means that it is at least as powerful as a Turing Machine  This means anything that can be computed by a Turing Machine can be computed by a Turing Complete system   No one has yet found a system more powerful than a Turing Machine  So  for the time being  saying a system is Turing Complete is the same as saying the system is as powerful as any known computing system  see Church-Turing Thesis

User · Answer

Here is the simplest explanation Alan Turing created a machine that can take a program  run that program  and show some result  But then he had to create different machines for different programs  So he created  quot Universal Turing Machine quot  that can take ANY program and run it  Programming languages are similar to those machines  although virtual   They take programs and run them  Now  a programing language is called  quot Turing complete quot   if it can run any program  irrespective of the language  that a Turing machine can run given enough time and memory  For example  Let s say there is a program that takes 10 numbers and adds them  A Turing machine can easily run this program  But now imagine that for some reason your programming language can t perform the same addition  This would make it  quot Turing incomplete quot   so to speak   On the other hand  if it can run any program that the universal Turing machine can run  then it s Turing complete  Most modern programming languages  e g  Java  JavaScript  Perl  etc   are all Turing complete because they each implement all the features required to run programs like addition  multiplication  if-else condition  return statements  ways to store retrieve erase data and so on  Update  You can learn more on my blog post   quot JavaScript Is Turing Complete quot      Explained

User · Answer

Its complete if it can test and branch  has an  if

User · Answer

Informal Definition  A Turing complete language is one that can perform any computation  The Church-Turing Thesis states that any performable computation can be done by a Turing machine  A Turing machine is a machine with infinite random access memory and a finite  program  that dictates when it should read  write  and move across that memory  when it should terminate with a certain result  and what it should do next  The input to a Turing machine is put in its memory before it starts   Things that can make a language NOT Turing complete  A Turing machine can make decisions based on what it sees in memory - The  language  that only supports    -     and   on integers is not Turing complete because it can t make a choice based on its input  but a Turing machine can   A Turing machine can run forever - If we took Java  Javascript  or Python and removed the ability to do any sort of loop  GOTO  or function call  it wouldn t be Turing complete because it can t perform an arbitrary computation that never finishes  Coq is a theorem prover that can t express programs that don t terminate  so it s not Turing complete   A Turing machine can use infinite memory - A language that was exactly like Java but would terminate once it used more than 4 Gigabytes of memory wouldn t be Turing complete  because a Turing machine can use infinite memory  This is why we can t actually build a Turing machine  but Java is still a Turing complete language because the Java language has no restriction preventing it from using infinite memory  This is one reason regular expressions aren t Turing complete   A Turing machine has random access memory - A language that only lets you work with memory through push and pop operations to a stack wouldn t be Turing complete  If I have a  language  that reads a string once and can only use memory by pushing and popping from a stack  it can tell me whether every   in the string has its own   later on by pushing when it sees   and popping when it sees    However  it can t tell me if every   has its own   later on and every   has its own   later on  note that      meets this criteria but      does not   A Turing machine can use its random access memory to track    s and    s separately  but this language with only a stack cannot   A Turing machine can simulate any other Turing machine - A Turing machine  when given an appropriate  program   can take another Turing machine s  program  and simulate it on arbitrary input  If you had a language that was forbidden from implementing a Python interpreter  it wouldn t be Turing complete   Examples of Turing complete languages  If your language has infinite random access memory  conditional execution  and some form of repeated execution  it s probably Turing complete  There are more exotic systems that can still achieve everything a Turing machine can  which makes them Turing complete too    Untyped lambda calculus Conway s game of life C   Templates Prolog

User · Answer

What i understand in simple words   Turing Complete   A programming language   program that can do computation  is Turing complete   For example      Can you add two  numbers using Just HTML   Ans is  No   you have to use javascript to perform addition    Hence HTML is not Turing Complete  Languages like Java   C    Python  Javascript  Solidity for Ethereum etc are Turing Complete because you can do computation like adding two numbers using this languages    Hope this helps

User · Answer

In the simplest terms  a Turing-complete system can solve any possible computational problem   One of the key requirements is the scratchpad size be unbounded and that is possible to rewind to access prior writes to the scratchpad   Thus in practice no system is Turing-complete   Rather some systems approximate Turing-completeness by modeling unbounded memory and performing any possible computation that can fit within the system s memory

User · Answer

Here s the briefest explanation  A Turing Complete system means a system in which a program can be written that will find an answer  although with no guarantees regarding runtime or memory   So  if somebody says  quot my new thing is Turing Complete quot  that means in principle  although often not in practice  it could be used to solve any computation problem  Sometimes it s a joke    a guy wrote a Turing Machine simulator in vi  so it s possible to say that vi is the only computational engine ever needed in the world

User · Answer

Fundamentally  Turing-completeness is one concise requirement  unbounded recursion   Not even bounded by memory   I thought of this independently  but here is some discussion of the assertion  My definition of LSP provides more context   The other answers here don t directly define the fundamental essence of Turing-completeness

User · Answer

I think the importance of the concept  Turing Complete  is in the the ability to identify a computing machine  not necessarily a mechanical electrical  computer   that can have its processes be deconstructed into  simple  instructions  composed of simpler and simpler instructions  that a Universal machine could interpret and then execute   I highly recommend The Annotated Turing   Mark i think what you are explaining is a mix between the description of the Universal Turing Machine and Turing Complete   Something that is Turing Complete  in a practical sense  would be a machine process computation able to be written and represented as a program  to be executed by a Universal Machine  a desktop computer    Though it doesn t take consideration for time or storage  as mentioned by others

User · Answer

A Turing Machine requires that any program can perform condition testing   That is fundamental  Consider a player piano roll   The player piano can play a highly complicated piece of music  but there is never any conditional logic in the music   It is not Turing Complete  Conditional logic is both the power and the danger of a machine that is Turing Complete  The piano roll is guaranteed to halt every time  There is no such guarantee for a TM  This is called the    halting problem

User · Answer

Can a relational database input latitudes and longitudes of places and roads  and compute the shortest path between them - no   This is one problem that shows SQL is not Turing complete   But C   can do it  and can do any problem   Thus it is

User · Answer

As Waylon Flinn said      Turing Complete means that it is at least as powerful as a Turing Machine    I believe this is incorrect  a system is Turing complete if it s exactly as powerful as the Turing Machine  i e  every computation done by the machine can be done by the system  but also every computation done by the system can be done by the Turing machine

[theory] What is Turing Complete?

Examples related to theory

Examples related to turing-machines

Examples related to turing-complete