2 ms·
This is a rather mundane and unsurprising line tbh. Finite automata are not Turing complete. Computers are not in reality since they do not have infinite memory
by godelski 3y ago
This is a rather mundane and unsurprising line tbh. Finite automata are not Turing complete. Computers are not in reality since they do not have infinite memory and do not have infinite precision. I'm not sure if it'll lead to arbitrary precision machines since the lack of real world Turing completeness hasn't stopped us so far and likely won't.
- TeMPOraL 3y agoIs there a formal, mathematical way of saying "real-world computers may not have infinite memory, but have more than enough, so they can be treated as Turing-complete for a subset of programs that are well-behaving - i.e. don't end up hitting the memory limit"? And in general, there surely is a way of formally saying "this is theoretically X, but effectively Y, for the [hand-waves] kind of inputs"?
- helen___keller 3y agoNot really, formal mathematics in complexity theory is involved when talking about asymptotics, constants like “for N < 10 trillion, a desktop computer is good enough” isn’t very interesting from a mathematical perspective. That said, some simple intuition is the following: PSPACE is a subset of EXP is a subset of EXPSPACE (We think these are all strict separations but technically that’s not fully proven) If you use the shorthand intuition that we can handle polynomial scaling but can’t handle exponential scaling, this means that we hit a time barrier (EXP-complete problems) before we hit a space barrier (EXPSPACE-complete problems) Another bit of intuition: you can store a very big number in very few bits in binary because binary holds an exponentially large number in linear bits. But you can’t loop over that number in a humans’ lifespan. Edit: > they can be treated as Turing-complete for a subset of programs that are well-behaving - i.e. don't end up hitting the memory limit Just to be clear, it’s a matter of input size and not the programs themselves. Technically you could say we haven’t “solved” sorting on real hardware because nobody can sort the first 2^1000 digits of pi. But realistically we don’t care to do so.
- maemre 3y agoSpace complexity helps characterize this: real-world computers can (arguably) emulate a linear-bounded automaton, so anything in DSPACE(O(n)) is fair game if you can wait long enough. For the arguably part: I am assuming that the machine can access all of the input at once, so it is reasonable to expect available memory to be a multiple of the input, so you get O(n) memory.
- godelski 3y agoI'm not a PL person or someone that focuses on computability, but I think you'd refer to it as "bounded," "pseudo," or "quasi." To give an example, you might call a transform on an image quasi-equivariant if it introduces some aliasing (obviously not destructing the image). See quasimorphism[0] as an example. Usually people just let it go unless someone brings up specifically something that implies that there is, or might, not a shared mutual understanding (as done here). Maybe it is shared, maybe not, maybe someone reading it doesn't understand the difference. I mean we're humans. We compress a lot of information into language that is not directly expressed in our words (this is also why it is often hard to talk to people on the internet since there's a wide audience with vastly different priors. Relevant XKCD[1]). [0] https://en.wikipedia.org/wiki/Quasimorphism https://en.wikipedia.org/wiki/Quasimorphism [1] https://xkcd.com/1053/ https://xkcd.com/1053/
- kaba0 3y agoComputers can do side effects so their state is effectively the universe. Which is still not infinite, but for all practical purposes the distinction doesn’t matter.
- kaba0 3y agoAn important distinction is that computers can do arbitrary many iterations of algorithms, while most neural networks have to operate on some fixed size, so the practical limits are very different.