Turing Complete

By Deane Barker • November 24, 2022 • 1 min read •

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 –

When something interesting has become accidentally Turing Complete. Meaning, it’s a specialized computing environment that has matured to the point where it can be used a general-purpose and has achieved Turing completeness. (Back to the above metaphor: it would be very interesting and worth mentioning that, “I modified this Roomba so you can drive it on roads!”)
To warn people that a particular language or environment is not for general purpose programming, lest they misunderstand. For example, it’s common to explain that HTML and CSS are not Turing Complete, in case someone thinks they can use them for more than just layout and styling. (The companion language of JavaScript, however, is very much Turing Complete. And with all the advancements in CSS, it might be inching towards Turing Completeness at some point – there is considerable debate and discussion on this topic.)

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.