News for hackers. Stuff that matters.

A comment on Accidentally Turing-Complete.

Re:Accidentally Turing-Complete by dane-pgp on Friday February 04, 2022 @10:11PM (#30216753)
One surprising example not listed there is "sliding-block puzzles", as proven in this paper:

https://groups.csail.mit.edu/mac/users/bob/sliding-blocks.pd...

[ Parent | on HN ]
Re:Accidentally Turing-Complete by stellaathena on Friday February 04, 2022 @11:55PM (#30217637)
This paper repeatedly states that it’s PSPACE, but I see no evidence that it’s Turing complete.
[ Parent | on HN ]
Re:Accidentally Turing-Complete by dane-pgp on Saturday February 05, 2022 @11:58AM (#30223038)
Sorry, you're right, yes.

> Technically, a problem is called PSPACE-complete if it is equal in computational power to a particular mathematical model of computation (called “polynomial-space-bounded Turing machines”).

[ Parent | on HN ]