What is Turing Complete?

theory turing-machines turing-complete
dlinsin picture dlinsin · Aug 10, 2008 · Viewed 185.8k times · Source

What does the expression "Turing Complete" mean?

Can you give a simple explanation, without going into too many theoretical details?

Answer

Mark Harrison picture Mark Harrison · Aug 10, 2008

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 "my new thing is Turing Complete" 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.

Related questions

What's a Turing machine?

What is a Turing machine and why do people keep mentioning it? My IBM PC is all I need to do my computation! Why does anyone care about these machines?

Read More
What is the difference between recursive and recursively enumerable languages

I was wondering what the difference between recursive and recursively enumerable languages is in terms of halting and Turing Machines. I know that recursively enumerable languages are a subset of recursive languages but I'm not sure about the difference beyond …

Read More
Difference between Turing-Decidable and Co-Turing-Decidable

I am really struggling with understanding the difference between these two. From my textbook, it essentially describes the difference by saying a language is co-turing recognizable if it is complement of a turing-recognizable language. I guess the part of this …

Read More