Hacker News Reader

Comment by zokier | Hacker News Reader

I'd argue the key difference between Turing machines and real-world computers is that computers do IO, respond to events, have real-time characteristics, and are interactive. All of these are key features in making computers useful, but are poorly (if at all) captured by Turing machine model. It's one thing to compute something, and another thing to play Doom.

View on HN

The key difference between Turing machines and real-world computers is that Turing machines have infinite memory. A real-world computer is thus not really a Turing machine, but rather a finite state machine.

You can have your I/O and Doom graphics on the Turing tape no problem.

What’s different is that accessing an arbitrary position on the tape isn’t O(1), like normally assumed for memory, On the other hand, memory (and address space) on real-world computers is finite, so you can always find a large-enough constant to make the Turing equivalent O(1) again.

There's an almost Turing equivalent mechanism that has no program counter and runs everything in parallel. I call it a BitGrid (it's my hobby horse). Because you can operate on all of the bits at the same time, you can get deterministic real time performance.

It's a systolic array of Look Up Tables, 4 bits in, 4 bits out, with a latch on each latched.

I/O is just built on top of the tape. Real computers reserve a map of memory to I/O.

This is like saying a CPU isn't a computer. It's sort of right but sort of wrong, you know?

Reply on news.ycombinator.com