News for hackers. Stuff that matters.
Re:Rice’s Theorem: An interactive tutorial by danbruc on Friday November 25, 2022 @09:55PM (#33749430)
Simulating it step by step is the upper bound establishing that is in EXPTIME, the second part, the reduction to the bounded halting problem, is what establishes EXPTIME-completeness. And the time hierarchy theorem finally establishes that EXPTIME is not equal to P.

There are no comments on this comment yet.