28 Sep Do you know a Turing Complete Language?
What Turing Complete Languages Do You Know?
First of all who asks this?
Well, I know someone because this is what I was asked recently.
It wasn’t in an interview setting or random quiz just someone throwing it out there at me. It’s exhausting even thinking about why someone would ask this in this way but hey I just tucked it away to add into my stand up comedy material (that’s the kind of material you can expect from me, terrible by all standards).
I knew they were speaking about Alan Turing but I honestly could not remember anything beyond the topic having something to do with calculus or at least I assumed it was or maybe it was time travel, by that point in the evening they were essentially the same thing. So me being me I just answered authoritatively, made some kind of joke and then just keep the conversation moving along (works about 80% of the time).
After getting home I had to actually refresh my memory and I found that I did, in fact, answer the person correctly. So what in the hell were they talking about when they asked about Turing Complete Languages?
Turing Completeness
In computability theory, a system of data-manipulation rules (such as a computer’s instruction set, a programming language, or a cellular automaton) is said to be Turing complete or computationally universal if it can be used to simulate any Turing machine. The concept is named after English mathematician and computer scientist Alan Turing. A classic example is lambda calculus.
Alan Turing
Alan Mathison Turing (23 June 1912 – 7 June 1954) was an English computer scientist, mathematician, logician, cryptanalyst, philosopher, and theoretical biologist. Turing was highly influential in the development of theoretical computer science, providing a formalization of the concepts of algorithm and computation with the Turing machine, which can be considered a model of a general purpose computer. Turing is widely considered to be the father of theoretical computer science and artificial intelligence.
Did you get all that?
So let’s break that down a bit, Alan Turing created a theoretical universal machine that would take an algorithm(set of instructions) and be able to process those instructions by following a set of steps or as Turning calls them states and it would look at symbols and find the value of that symbol then continue on to the next state until it hits a final state where it writes down an answer. So all it does is Read, Write, then Print. So essentially Turing says that instead of having all the complexity live inside of a physical machine requiring separate machines for each type of operation you’d like to perform, the complexity would live inside the set of instructions / the algorithm that then is read by the machine and processed.
So what is turning complete language?
As explained by Professor Brailsford:
So ultimately we know that anything that takes a program and is able to run it is a Turing Machine and if that thing is able to run algorithms that a Turing Machine can run then that in itself is Turing Complete. So yeah, almost all programming languages are indeed turning complete.
Also published on Medium.