4 ms·

> so for a sufficiently complex property you would effectively have to iterate over this problem space. Why? Why are you assuming that the only way to figure

> so for a sufficiently complex property you would effectively have to iterate over this problem space. Why? Why are you assuming that the only way to figure out if a program halts is by simulating running it step by step? And not by analyzing the description of the program?

kaba0 4y ago
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
- wizeman 4y ago
  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?
  - kaba0 4y ago
    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?
    - wizeman 4y ago
      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 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.

kaba0 4y ago

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

wizeman 4y ago
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?
- kaba0 4y ago
  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?
  - wizeman 4y ago
    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 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.