There are many references to it in public discussions, but trying to learn about it from Wikipedia is like reading in a new foreign language.
In: 283
[removed]
Even today, there are computational machines (computers) that have specific uses. For example,
* a cheap calculator can only do arithmetic
* a doorbell can only play a couple of tunes
* a dumb-phone can only be used for calls and SMS
These machines are incapable of handling any other set of instructions (try instructing your doorbell or dumb-phone to play Netflix!) that is not pre-built into its hardware.
Then come general-purpose machines. These are capable of handling a wider variety of tasks provided you can supply it with the algorithm (set of instructions) to solve that task. Alexa speakers, smart TVs, and laptops are a good examples of general-purpose machines. Whenever you install an app on these devices you are supplying an algorithm under the hood.
Ok, so a smart TV and a Macbook are both general purpose machines. But surely you do expect a smart TV to do all the tasks that are possible to do on a laptop? That is because all general purpose machines are not alike. They have different limitations which can be classified as:
* hardware limitations and
* conceptual limitations.
Hardware limitations are well understood — the device runs out of gas due to low memory or CPU cycles.
Conceptual limitations are due to system design. If a devise is designed to not handle a particular algorithm no amount of upgrading of RAM or CPU will help. Conceptual limitations can arise due to the operating system of the device or the programming language used in the device.
If you have understood so far, defining Turing machines will be easy. A **Turing complete machine** is a machine which has NO Conceptual Limitation. If you can provide a set of instructions it will get the task done. The task may take an infinite amount of time because of the hardware limitation, but it will get done. You just have to wait long enough. Upgrading hardware will help.
Since nobody runs all possible algorithms on each computer unit just to prove that it is Turing Complete, mathematics is used to prove the same. Maths is a strange thing. You can prove a concept long before its physical manifestation. Alan Turing did this before the evolution of modern computers (just like Einstein gave us relativity without time-traveling).
Today we talk about Turing completeness when designing programming languages. Most modern programming languages are turing complete (Python, Java, C++ etc). It means that they are capable of executing any algorithm known to mankind. Hardware is an afterthought — if it can run these languages it is good.
Microsoft Excel formulae were not turing complete until 2021. Now that they are, you can rest assured that there is a way to solve that problem in Excel no matter how ugly the formula becomes.
Hope that helps!
Latest Answers