News for hackers. Stuff that matters.
Re:Baba Is Turing Complete: A Sketch of a Proof by taneq on Wednesday May 15, 2019 @06:25AM (#19917998)
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.

Re:Baba Is Turing Complete: A Sketch of a Proof by mannykannot on Wednesday May 15, 2019 @07:14AM (#19918264)
It 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.

Re:Baba Is Turing Complete: A Sketch of a Proof by taneq on Wednesday May 15, 2019 @08:49AM (#19918844)
I guess I was hoping for a snappy term like "finite Turing-complete" or something.
Re:Baba Is Turing Complete: A Sketch of a Proof by theoh on Wednesday May 15, 2019 @01:23PM (#19921662)
The "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.

Re:Baba Is Turing Complete: A Sketch of a Proof by davidgrenier on Wednesday May 15, 2019 @06:43AM (#19918089)
Closest 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

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.

Re:Baba Is Turing Complete: A Sketch of a Proof by mannykannot on Wednesday May 15, 2019 @07:41AM (#19918402)
At 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.

Re:Baba Is Turing Complete: A Sketch of a Proof by Retra on Wednesday May 15, 2019 @04:08PM (#19923210)
I 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.
Re:Baba Is Turing Complete: A Sketch of a Proof by empath75 on Wednesday May 15, 2019 @07:52AM (#19918474)
Every 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.
Re:Baba Is Turing Complete: A Sketch of a Proof by barbecue_sauce on Wednesday May 15, 2019 @02:41PM (#19922415)
But with that line of reasoning, would there be anything that is actually turing complete?
Re:Baba Is Turing Complete: A Sketch of a Proof by mcphage on Wednesday May 15, 2019 @03:27PM (#19922840)
Just mathematical constructs.