Rice’s Theorem: An interactive tutorial

Re:Rice’s Theorem: An interactive tutorial by kaba0 on Friday November 25, 2022 @03:11PM (#33746270)

You can analyze it, and for that you would use some system like logic. But it so happens that these pesky mathematicians are everywhere, because any sufficiently complex system will fall victim of Gödel. And in fact, Math itself is limited and trivially overstepped by Turing machines, but you are free to create any other reasoning system, it will also fall short of Turing.

So, will you believe that these people (I believe Gödel was praised highly by even Neumann!) weren’t talking out of their asses? :D

[ Parent | on HN ]

Re:Rice’s Theorem: An interactive tutorial by wizeman on Friday November 25, 2022 @03:17PM (#33746325)

Gödel proved things about the limits of math and logic.

What does that have to do with how long a specific algorithm takes to run?

[ Parent | on HN ]

Re:Rice’s Theorem: An interactive tutorial by kaba0 on Friday November 25, 2022 @04:10PM (#33746801)

Well, if not by running them and not by analyzing them (any rule system, not just logic is affected), what is your proposed.. whatever to say whether they halt or not? Or any other non-trivial, semantic property?

[ Parent | on HN ]

Re:Rice’s Theorem: An interactive tutorial by wizeman on Friday November 25, 2022 @04:22PM (#33746917)

Sorry, I think I had misinterpreted your point.

So you're saying that there are only 2 options:

1. You either simulate running the program step-by-step (which has an extreme time complexity problem).

2. Or, you try to analyze it within some system of logic. But if you do so, then there are things that you can't prove because logic itself can't prove certain statements.

This is an interesting argument. But I think point 1 sort of disproves point 2.

Point 1 means that you can always analyze such algorithms, it's just that it might take a really long time to achieve that.

So I think point 2 is not valid in this specific context. Because you can always prove whatever you want (given that when you simulate running a program, you are necessarily doing it within a system of logic), it's just that we don't know how long that could take in theory (of course, in practice, it's currently intractable).

So if you can always prove whatever you want, that means Godel's results about the undecidability of certain statements don't apply when analyzing finite-state systems, only infinite ones.

[ Parent | on HN ]