wizeman

31 ms·

181.
by 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
182.
by wizeman 4y ago
I agree a bit with your point, but still, given how little it is usually emphasized that the Halting problem is not valid for finite-state machines I'm not sure that even very smart people don't mistakenly end up believing that it
183.
by wizeman 4y ago
> It's not possible to write an algorithm that will detect infinite loops in all programs. Actually, it is possible, if the program is not allowed to consume infinite memory. That's what these algorithms do (where "value&q
184.
by wizeman 4y ago
Agreed!
185.
by 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?
186.
by wizeman 4y ago
> You answered your question as you asked it. If you juice up your Turing machine like that, it will still suck so much that nobody will actually write programs for it, but it will be more complicated to describe and analyse. Of course.
187.
by wizeman 4y ago
> Caveat, the thing that makes it decidable is not the fact that it was going to run on a computer with finite memory, the SMT solver will fail on many code chunks that can run on your computer. And what does that say about the problem,
188.
by wizeman 4y ago
> I don't agree at all. I do static analysis for my career. Trying to model the actual set of available memory configurations of a physical machine is going to scale way way way worse for most meaningful problems than approaching th
189.
by wizeman 4y ago
> Great. And the entire field of static analysis is available for you to do this. But when discussing the formal consequences of the halting problem it is just completely pedantic to show up and point out that actually you can run Coveri
190.
by wizeman 4y ago
> Now you are just back at the Halting theorem, and thus Rice’s theorem. How so? We know the Halting theorem and Rice's theorem to be decidable for finite-state machines, so how does that prove anything about the time complexity of
191.
by wizeman 4y ago
> But often mathematical models are more informative and interesting than the concrete physical objects they abstract. Yes, I agree. But a model of a machine with finite states is more informative and interesting for applying it to real-
192.
by wizeman 4y ago
> 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 ana
193.
by wizeman 4y ago
> Either you know weaknesses in the crypto system, or you have no choice but to iterate though each key to see if the output matches the phrase. > There is a relationship with proof of work crypto as well. Even all the Bitcoin mining
194.
by wizeman 4y ago
> effectively turning the whole universe into one Not the whole universe, exactly. Just the parts that are possible to access :) > I’m not really sure it is a good rebuke of the Halting problem that “we can brute force our way out of
195.
by wizeman 4y ago
> You asked if we could solve if it overflows a computer efficiently (without overflowing it), so I am showing that is not possible generally due to limitations of math; both our current understanding but also because math also has limit
196.
by wizeman 4y ago
> Let us for simplicity assume that in every step only one bit of state gets accessed, this will only be wrong by some constant factor. With that running a Turing machine for at most n steps will ensure that it does not use more than n b
197.
by wizeman 4y ago
No, it does not provide an answer. What does that have to do with analyzing a finite-state machine in EXPTIME-complete time? The busy beaver problem, again, assumes it is running on a Turing machine with infinite memory. Don't confuse
198.
by wizeman 4y ago
> we can write a program that only halts if counter example is found, and we would be unable to prove if the program halts. Yes, but again, you're missing my point: you would be able to prove if the program halts. It's just t
199.
by wizeman 4y ago
> - Unbounded memory is always assumed for analyzing complexity. If not, all algorithms on all computers are O(1)... which is more or less the line of inquiry you seem to be going down. All algorithms being O(1) is not a useful measure o
200.
by wizeman 4y ago
> Deciding whether a finite Turing machine - a.k.a. a real computer - halts is EXPTIME-complete Can you point me somewhere that proves this exact statement you're making? Or at least, explains why it is true. I'm interested in
201.
by wizeman 4y ago
> There are worse complexity classes than NP, for example EXPTIME, which we know are not P by the time hierarchy theorem. I mentioned this in another comment: isn't EXPTIME only defined for Turing machines? Which again, just touches
202.
by wizeman 4y ago
> EXPTIME complete Isn't EXPTIME completeness only defined for Turing machines? Which again, just proves all of my points. For all we know, if you've reached the conclusion that an algorithm is EXPTIME-complete, this conclusion
203.
by wizeman 4y ago
> the halting problem of Turing machines with state space of N bits That's an oxymoron, because Turing machines have a state space of infinite bits by definition. I understand you mean "deterministic finite-state machines"
204.
by wizeman 4y ago
> Proving it always halts (or crashes) in some fixed amount of memory is insufficient for saying anything meaningful about the program: we oftentimes care about the mathematical object a computer is modelling, not just the computer itse
205.
by wizeman 4y ago
> There are so many bits of state in a modern CPU, you are never going to solve the halting problem in practice even for a computer with a CPU only but no RAM or disk. And once you add some RAM, or haven forbid, a disk with a couple of t
206.
by wizeman 4y ago
I'm sorry, I've only gone through the first few steps of the tutorial but the initial claims have already bothered me a lot. I have to be pedantic because this is the biggest pet peeve of mine: > Turing famously showed that com
207.
by wizeman 4y ago
> with every model I’ve tested there’s a set of errors that would virtually never be made by any human I guess you've never seen my drawings...
208.
by wizeman 4y ago
mlock() forces pages which have already been allocated and are already being used within an address range to stay resident in memory, so that they are not swapped out to disk. These pages were already being accounted for in swap reserva
209.
by wizeman 4y ago
Except it's not really a "zero sum game with an ever increasing pie". Even if the pie remains exactly the same, it's not a zero sum game: simultaneous value for two people can be created out of nothing simply by the volu
210.
by wizeman 4y ago
That's not zero sum. The pie can be 100% finite and yet, while everything else remains equal, two people can both benefit and be happier at the same time by simply (and voluntarily) exchanging a good or service between them, because th

More ›