4 ms·
huh? - so we can never build turing machines? because we can never build infinite memory?
by xaedes 9y ago
huh? - so we can never build turing machines? because we can never build infinite memory?
- schoen 9y agoTrue, no Turing machine in the strict sense is physically realizable!
- gnulinux 9y agoYes, computers are not Turing machines but finite state machines. But in practice, this is not very useful since the number of states of a computer is huge, so, Turing machine is a good model for computers. In math, we're not interested in physical objects but models and it turns out the study of Turing machines can be applied to physical computers. When you think of computer, you do not think it as finite state machine, but as a Turing machine. Maybe if you had a machine with 1KB memory, you could think it as a finite state machine, if it's more useful. Another thing is, most algorithms people deal with are O(1) since people are interested in ints which can represent -2^63 to 2^63-1. But this is just an abuse of terminology, an algorithm that tries all 2^64 combinations would be a very impractical O(1) algorithm. So, we instead use a different model, and pretend integers are arbitrarily long and their length is O(logn) bits. This is now a better model for physical computers.
- Retra 9y agoSure. But anything a turing machine could calculate in finite time can be calculated using finite memory, so this doesn't matter unless you're trying to compute things that don't end.