Posted on 23 November 2021, by Kevin Mora
A Turing Complete system is one where a computer program can discover the solution (although, with no guarantees regarding runtime or memory).
Alan Turing created a machine able to take a program, run it, and show some result. In those days, Turing and other early computer scientists would have to build a specific machine each time they wanted to solve a specific problem (e.g., a colossal machine with the size of a car able to exclusively add numbers, nothing else). If by any chance you wanted to substract, multiply or divide integers, you'd have to create another colossal machine for each operation – machines with a single purpose, as opposed to now that we have a single machine that can be forever reprogrammed.
For that reason, he created the "Universal Turing Machine," able to take any program and run it. Programming languages are similar to those machines (although virtual) – they take programs and run them. A programing language is called "Turing complete," if it can run any program (irrespective of the language) that a Turing machine can given enough time and memory.
As an illustration, suppose there is a software that adds 10 numbers. This program can be easily run on a Turing machine, but assume that for some reason your programming language is unable to perform the same addition. As a result, it would be "Turing imperfect". On the other hand, if it is Turing complete if it can execute any program that the all-purpose Turing computer can execute.
Most modern programming languages are all Turing complete because they each implement all the features required to run programs like addition, multiplication, if-else conditions, return statements, ways to store/retrieve/erase data and so on. The purpose of this simplification is to make theory issues (like halting problems, complexity classes, and other issues that theoretical computer science is interested in) simple to think about. One specific advantage is that it is typically very simple to test whether a particular computer or language can simulate a Turing machine by simply programming the Turing machine in question in that language.
A Turing machine can take decisions based on what it sees in memory – the "language" that only supports +, -, *, and / on integers is not Turing complete because it can't make a choice based on its input, but a Turing machine can. Therfore, these machines can run forever – if we took Java, C++, or Python and removed the ability to do any sort of loop, GOTO, or function call, it wouldn't be Turing complete because it can't perform an arbitrary computation that never finishes. A Turing computer can use infinite memory – take for instance Java; it has no limitations that prevent it from using infinite memory, and it is still a Turing complete language even though we are unable to construct a true Turing machine due to space limitations. That's why regular expressions aren't Turing complete.
A language that only allows you to access memory through push and pop operations to a stack wouldn't be Turing complete because a Turing computer has random access memory. These machines can also mimic any other Turing machine; given the right "program," a Turing machine can take the "program" of another Turing machine and simulate it using any input. It wouldn't be Turing complete if a Python program couldn't be implemented in a language. If you had a language that was forbidden from implementing a Python interpreter, it wouldn't be Turing complete.
Keep in mind that neither time nor storage can ever be limitless; they are both unbounded. Every unique computable run will have a maximal value for them, but there is no upper bound on the size of that value. It is glossed over that a real computer will eventually run out of RAM; this is obviously a limit for any physical computer, but it is also clear and unrelated to the machine's theoretical "computing capacity." Additionally, we are not at all concerned with how long it truly takes. As a result, our tiny machine is completely impractical because it can utilize any quantity of time or space.
Therefore, a Turing machine is a device with infinite random access memory and a finite "program" that specifies when it should read, write, and move across that memory, when it should end with a specific outcome, and what it should do next.
There is some possibility that a black hole could be used as a computing device – an extremely fragile and dangerous one. The solution is read back as Hawking radiation after being encoded as infalling matter – a truly unrealistic and bizarre technique of universal computation.