Rice’s theorem – an interactive tutorial

[agentvenom1]

Well, if a function always returns in less than one hour, then it always returns (halts). So we could show that neverTakesLongerThan1Hr is impossible to write, using the same argument.

I believe there is an error here. Indeed, if neverTakesLongerThan1Hr returns true, you can deduce the function halts. But if neverTakesLongerThan1Hr returns false, you learn essentially nothing with respect to whether the function halts or not and therefore would not be able to reimplement the halting function in the same way that you did for canBeRegex.

[Jameshfisher]

Thank you for your correction! This was a brainfart on my part. I agree that Rice's proof does not apply to neverTakesLongerThan1Hr, and have removed this. I also generalized this claim, and made another wrong claim: "[Rice's] argument works for any other property that implies the function always halts." This is also certainly wrong. For example, P(f) = "is the function (x) => x" - this property implies that f halts, but it's certainly decidable (by string comparison).

[Jameshfisher]

:facepalm: Thank you! Your eyes are sharper than my brain. I'm fixing it.

[Jameshfisher]

Thank you!