Turing Complete

This is description or a certification of a programming language. It’s named for Alan Turing, the computer scientist that theorized about it in the 1930s and 40s.

There are two definitions –

A formal definition, which is complicated and involves a hypothetical “Turing Machine” that solves computational problems. This was theorized to be the “universal” computational engine that can solve any problem that can be computed. If your language can do everything a Turing Machine can do, it’s considered “Turing Complete.”

An informal definition, which just means your language is a generally competent programming language.

You would never bother to mention that Java or C# is Turing Complete, because this is just a given – any language designed for general purpose usage is going to have if/then statements, variables, looping, etc. which are required to solve computational problems. Of course they’re Turing Complete – they were designed to be this way.

That would be like saying, “You can drive this car on roads!” Well, of course you can – this is what cars are made for.

There are only two situations when you would make a point of whether something is Turing Complete –

At the bottom of its article on Turing Completeness, Wikipedia lists some environments that have achieved unintentional Turing completeness over time and development, like Excel, PowerPoint, and even Minecraft. This means that you can technically use the logical processing abilities in Minecraft to solve any computational problem, as wildly inefficient as this might be (example: someone “built” an 8-built CPU inside Minecraft).

Turing Tarpit is a phrase meaning a language which is technically Turing Complete but is difficult and useless for most tasks.

Why I Looked It Up

I had a vague idea of what it meant, but I wanted specifics. Unfortunately, the only specifics to be had are an understanding of the Turing Machine theory, which didn’t shed any new light on what I already understand – Turing Complete means something can be used for general purpose computational resolution.

This is item #485 in a sequence of 520 items.

You can use your left/right arrow keys to navigate