| ▲ | olmo23 3 hours ago | |||||||
Also check out https://en.wikipedia.org/wiki/Rice%27s_theorem basically generalized the halting problem to arbitrary semantic properties. | ||||||||
| ▲ | tialaramex an hour ago | parent [-] | |||||||
It's convenient that Henry Rice lived long before the age of language cults. I don't even think Rice wrote software, he's just a mathematician, he proved this nice property in mathematics. Stuff like FORTRAN and ALGOL happens later. Also though, just as for the Halting Problem, we are always allowed a three-way split. Rice proves that "Has property" vs "Does not have property" can't be done, but "Has property" vs "Does not have property" vs "Shrug - I dunno, seems hard" is possible, and indeed easy if you're OK with lots of machines landing in the "Shrug" pile. You can expend as much work as you like to shrink that pile, Rice just proved it would need infinite work to empty it completely. | ||||||||
| ||||||||