Hand-drawn picture of Turing Machine

What does "Turing Complete" mean?



The question of whether something is "Turing Complete" or not usually pertains to computer languages. A computer language is Turing Complete if you can use it to write programs to simulate any Turing Machine. Most computer languages are Turing Complete, but there are some that aren't.

In order for a language to be Turing Complete, it must have the ability of storing information somewhere, and also the ability to retrieve that information as data. It must also have conditional branching in order to be able to simulate the Turing Machine's ability to move to another state.

Most computer languages, including Fortran, Cobol, Basic, C, etc., have these abilities and are therefore Turing Complete.

An example of a language that is not Turing Complete is HTML which you can use to create a web page. It's not a Turing Complete language because it lacks conditional branching. (However, when HTML is used with JavaScript, then we do have Turing Completeness, because we now have the conditional branching and looping that comes with JaveScript. Furthermore, HTML with just CSS can also be Turing Complete, but that's a much more complicated topic.)

If you had downloaded the Excel file from the Home Page of this website, and if you had built and run some Turing Machines using it, then you might think that Excel is Turing Complete. Well, actually, it's more correct to say that Excel VBA is Turing Complete, because the program that actually built and ran the Turing Machine for you was written in the Excel VBA language.

By the way, Felienne was able to run a Turing Machine in Excel without even resorting to Excel VBA, but just using the Formulas that are readily available in Excel.

Version 1.0 -- April 23, 2017
Template Version 1.0 -- May 19, 2017