4 ms·
It's hard to analyse devices like this. It's clearly not Turing complete but it isn't a Turing machine. It can clearly compute any output for any given input (l
by barbegal 6y ago
It's hard to analyse devices like this. It's clearly not Turing complete but it isn't a Turing machine. It can clearly compute any output for any given input (like a programmable logic array) but it can do a bit more given it can have several bits of internal state.
- dmitrygr 6y agoIt is a DFA plan and simple
- anoncake 6y agoSo is every computer. 2^(RAM size in bits + Caches size in bits + Registers size in bits + stuff I forgot) is a finite number of states.
- Dylan16807 6y agoTuring machines are a minimal model that don't map easily to normal computers. This, on the other hand, is a very normal computer. It's just that it has an extremely small amount of memory. If you put a RAM chip between those output wires and input wires then it could be Turing complete.
- charcircuit 6y agoRAM chips have finite memory. It still won't be Turing complete.
- freeone3000 6y agoTuring complete, in common usage, refers to the ability of finite Turing machines, not infinite ones, since any machine we physically built are built according to physical laws.
- Dylan16807 6y agoIf the RAM fills up then swap it with a bigger chip behind the machine's back. And for any calculation you expect to complete on a physical device, the computational difference between finite and infinite memory is basically nothing.