News for hackers. Stuff that matters.

A comment on Accidentally Turing-Complete. Parent comment

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 ]