Well, I may be writing stupid things in the following, but have a look at the Busy Beaver problem. Even for tiny tiny state sizes it will grow faster than any computable function — so for a sufficiently complex property you would effectively have to iterate over this problem space. No matter if even P=NP, that is just.. literally bigger than any function you could make up.
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
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?
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 programs, 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 computation systems, only infinite ones.
