Re:What is the enlightenment I'm supposed to attain after st...
by chas on Sunday November 24, 2013 @06:06PM
(#6791600)
A PC can still read and write from arbitrary memory locations which means it can know a lot about it's past states, so the memory limit makes it a deterministic linear-bounded automata.
Re:What is the enlightenment I'm supposed to attain after st...
by andrewaylett on Monday November 25, 2013 @03:14PM
(#6796618)
But the LBA is limited to the size of the input string, while a PC has a fixed but insanely large number of states (2^{number of bits of storage}) and can't in theory accept arbitrarily large strings.
In the somewhat twisted view of the machine I'm putting forward, it's not accessing 'arbitrary memory locations' as memory locations, rather the content of that memory location is part of the input state.
For all practical purposes, your PC adequately models a Turing machine. In point of literal fact, it doesn't because it only has finite storage. In practical usage, it is sometimes helpful to consider various states your code may enter and how they interact. For understanding how the system actually works, the author appears to have found the state-switching model to be a useful one, and indeed I understand that it's common to model the internal state of various devices using finite automata.