3 ms·
We can't create an algorithm determining whether a computer program halts or not, but we can write one that checks whether it conforms to natural language speci
by soraminazuki 5mo ago
We can't create an algorithm determining whether a computer program halts or not, but we can write one that checks whether it conforms to natural language specifications much more easily? That makes no sense. There's no exception to the halting problem regarding "human comprehensible" computer programs.
- __s 5mo agoThey're saying most useful programs don't fall in the complete / correct divide. You can get a lot done while restricting yourself to provable programs
- wizzwizz4 5mo agoRice's theorem says that we can't draw a partition between two sets of programs, based on their semantic properties. It says nothing about drawing a partition slightly to one side of the desirable partition, misclassifying some tricksy cases, but correctly classifying all the programs we care about.
- deleted 5mo ago[deleted]