4 ms·
That's pretty neat. Is there a name for the thing where you generalise something to be an infinite version of itself, then show that that infinite version is T
by taneq 8y ago
That's pretty neat.
Is there a name for the thing where you generalise something to be an infinite version of itself, then show that that infinite version is Turing complete, then transfer that back to the original finite thing? Sort of like we are willing to call real physical computers 'Turing complete' despite them clearly not having infinite memory.
- davidgrenier 8y agoClosest thing I could find was involved in proving the finite version of Ramsey's Theorem from the infinite version as a compactness argument. https://en.wikipedia.org/wiki/Compactness_theorem https://en.wikipedia.org/wiki/Compactness_theorem That being said, I'm a little curious as to why one would want to prove something is Turing complete. I tend to assume something is Turing complete unless shown otherwise. For instance, I would never have gambled MTG wasn't Turing complete.
- mannykannot 8y agoAt the very least, proving that a game is Turing complete can be as entertaining a challenge as playing it. One case where Turing completeness was useful was in proving wrong those programmers who claimed that there were some programs that just could not be written using structured programming. Also, if we did not know about Turing completeness, there would be constant futile research trying to find alternative architectures and languages that could solve problems that cannot be solved with what we have.
- Retra 8y agoI think it is probably more useful to prove that something isn't Turing complete, and explain why. Finding things that are Turing complete is the basically the same task through a complementary lens.
- mannykannot 8y agoIt is more or less obligatory to do it this way; if you tried to avoid generalizing to an infinite version, you would have to qualify various arguments with something like "assuming sufficient resources...", which amounts to the same thing. No finite state machine is strictly Turing-complete, but the category of those that would be, but for the resource limitation, is an extremely useful one.
- taneq 8y agoI guess I was hoping for a snappy term like "finite Turing-complete" or something.
- theoh 8y agoThe "generalizing" process is called idealization. Whenever Turing machines are mentioned, it's an idealized version of a machine that is being referred to. Every finite physical machine is limited in different way, so it doesn't make much sense to try to lump them together. Whereas every Turing-complete machine is equivalent.
- empath75 8y agoEvery time someone says something like minesweeper or PowerPoint is turing complete, some pedant will chime in that it isn’t, because it doesn’t have an infinite board/slides/whatever.
- barbecue_sauce 8y agoBut with that line of reasoning, would there be anything that is actually turing complete?
- mcphage 8y agoJust mathematical constructs.