Re:Magic: The Gathering Is Turing Complete (2012)
by xaedes on Thursday November 16, 2017 @02:09PM
(#15715520)
huh? - so we can never build turing machines? because we can never build infinite memory?
[ Parent
| on HN ]
Re:Magic: The Gathering Is Turing Complete (2012)
by gnulinux on Thursday November 16, 2017 @07:25PM
(#15717991)
Yes, 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.
Re:Magic: The Gathering Is Turing Complete (2012)
by schoen on Thursday November 16, 2017 @02:25PM
(#15715682)
True, no Turing machine in the strict sense is physically realizable!