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:

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

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

Post a Comment