3 ms·
A model takes a fixed length input and returns a fixed length output in finite time, it's not Turing complete
by capitalsigma 4y ago
A model takes a fixed length input and returns a fixed length output in finite time, it's not Turing complete
- roywiggins 4y agoJust equip it with a paper tape, give it the current cell and state as input and use the output to decide whether to move the tape or write to it. I'm sure you could encode a universal TM in a handcrafted neural net this way. Maybe it's cheating, but after all, this is the only way humans can do universal computation- we can't hold an infinite tape in our head either, and neither can a CPU, we have to give it sufficient scratch space to act as the tape. Alternatively, perhaps there's a (very large) neural net that can prove things about Turing machines that aren't too large. It only has finite input and finite output (it's not Turing complete) but it can prove stuff about smallish Turing machines, providing the proofs aren't too long. That seems reasonable, because that's what humans do when we prove stuff about Turing machines! Perhaps neural nets could never actually do this, either they're fundamentally not capable or we never work out how to actually find one that does, but it seems possible?