3 ms·
Quite a comprehensive summary of the implications of Turing-Completeness. There aren't any outright errors that pop out to me which is high bar if other article
by thethirdone 3y ago
Quite a comprehensive summary of the implications of Turing-Completeness. There aren't any outright errors that pop out to me which is high bar if other articles are anything to judge by.
> This was “easy” because the other major thing about UTM’s is how well they generalize to proving that just about any property of an algorithm is not computable, in the general case.
This paraphrasing of Rice's theorem is good enough, but the mathematical result is meaningless in the practical Turing Complete sense. Rice's theorem is misused often on the internet to put limits on static analysis, but in most cases you can successfully prove that a given program terminates. And by proving that, Rice's theorem no longer prevents you from proving anything.
> That looks like an unprovable property, which is exactly what you would have in a Turing-complete language.
> ...
> In essence, your language is still Turing-complete in practice.
The implication of this statement is that because it is not obvious how to prove a given statement, it must be impossible to prove ANY statements in the general case. No additional argument beyond Rice's theorem has been given to explain why proving other properties would be impossible in the general case.
It is exactly this thought process that makes me strongly dislike Rice's theorem. It is easy to decide that "I must not be able to prove this because its impossible" even when it is practically provable.