I just can’t understand no matter how much I google it.
In: 6
Turing completeness is, basically, “can compute anything you can write an algorithm for, given enough time”. Or, more simply, “can run an emulator of a turing machine, so anything a turing machine can compute, so can the thing”.
Turing completeness refers to how capable a language is. A Turing-complete computer or language can run a complete simulation of another computer or another language. In other words, it can “understand” both the code it’s written in **and** code that is given to it.
A non-Turing complete device might be something like a calculator. It only understands its own code, so it can only do math. If you gave it code to write out text, it won’t work; it doesn’t recognize the code, so it cannot execute it. It can only process numbers and mathematical operations.
A Turing-complete device would be a virtual machine or an emulator. The virtual machine is not a real computer; its the computer running software that simulates a real computer. However, if you were to start a program within the virtual machine, the software will say “This is a program with a bunch of code in it. I will execute the code within the program.” The software has the ability to react to independent programs as if it were a separate computer running the program. It can understand the program’s code and execute it.
Way back, before the modern idea of a computer had been invented, Alan Turing came up with an idea for how computers might be built. This is called a Turing machine. His idea was kinda weird in retrospect, but it’s quite simple. Despite being simple and weird, it’s been shown that a Turing machine can do anything a modern computer can do.
A programming language is called Turing-complete if you can write a Turing machine simulator in it. Thus, that programming language can do anything a Turing machine can do, and thus it can do anything that any other programming language can do.
Turing complete means you can build a “Turing machine”, and a Turing machine is effectively a computer that is stripped from all “fancy stuff”. Basically the most abstract form of a computer. You can then take that super basic machine and show how it can do more complex things (with enough programming), and you can then keep building on it until you reach an actual “modern” computer.
It basically goes like this:
> a simple computer has a 32 bit bus to binary ram. But do you really need 32 bit? You can do the same things with 8 bit (albeit slower), but you could do the same thing with 2 bits; 1 bit?, albeit slower etc.
> a simple computer has a processor with 100 instructions. But do you really need all these instructions? You can probably “program” some instructions with other ones (albeit slower, or in a roundabout way).
>a simple computer can add 32 bit numbers. But you can probably do the same with two separate 16 bit numbers (with some extra math) etc. 4 bit? Individual bits?
As you break down the bare minimum that a computer needs, it basically comes down to a piece of memory (usually modeled as a paper ribbon with symbols), a way to read/write to the memory (one symbol at a time) usually modeled as a “writing head” like a type writer. And a way to move the address where to read/write left and right.
Then the rest would just be a super basic “language” that holds all the logic, which can be mathematically boiled down to a “state machine”. Which is effectively a flow diagram you walk through, with basic rules on how to “follow the arrows” on the flow diagram. There are multiple models you can use, but they all come down to the same super basic thing (and you can show that you can “translate” these models to each other with no loss of functionality.
Penning down this super basic “minimum set” that describes a “computer” is very powerful, because it turns out you can build a Turing machine with very unexpected simple elements, like a marble track, twigs and stones or even just a pen and a piece of paper etc. (It would require massive amount of materials and manual labor to “run” the computer, but it is theoretically possible, and you can then just take for granted you can build a “real” computer with it e.g. the classic “can it run doom?”. Answer: yes..)
This is kinda how people approach running doom in Minecraft etc. You do the relatively simple check to see if you can build a Turing machine. If you can, you know it is just a whole bunch of work and complexity to run Doom, or Crysis, or Windows – the complexity makes no difference, aside from work and time.
Latest Answers