I just can’t understand no matter how much I google it.
In: 6
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