Friday, September 25, 2009

What does Turing Complete mean?

Consulting the magnifluous fount of perpetual enlightenment:

Turing completeness:

A computational system that can compute every Turing-computable function is called Turing-complete (or Turing-powerful). Alternatively, such a system is one that can simulate a universal Turing machine.


Thank you, circular definitions.

In English:


A turing-complete programming language is a "real" programming language. The quick test is whether it has control structures that can go backwards: loops and/or recursion. That's pretty much it.

Examples:


C/C++, Java, Python, Ruby: Yes
a calculator: No
spreadsheet formulas (Excel, etc.): No
Lisp, Haskell, Prolog: Yes
assembly languages: Yes

Who cares:


The big deal with turing-complete programming languages is that any problem you can solve with one of them, you can solve with any other of them. So you could theoretically write gcc in BrainF if you had enough patience and system resources. You cannot, however, write gcc in Excel formulas.

2 comments:

Jose said...

Again, you save the day. That was very helpful :D

Roy van de Water said...

You should be able to pull off writing gcc in VBA for MS Excell