Comment

Comment by ThreeFx

Not really, because for undecidable problems semidecidability can only hold one-way. If it held in both ways then the language would be decidable.

Take the Halting program for example: For a program p which halts, you can determine whether it will halt in finite time (because by definition it halts). However, there is no semidecidable algorithm for "this program runs infinitely long".

parent ThreeFx 5 years ago

Discussion

Live from the official Hacker News API

A modern reader for Hacker News · SvelteKit + Skeleton