wizeman

20 ms·

151.
by wizeman 4y ago
Another one, imitating a Twitter thread: > Write a satirical example of a Twitter thread about a news story. Thread: 1. BREAKING: A study has found that the air in major cities is now so bad it causes permanent brain damage! 2. Scientist
152.
by wizeman 4y ago
Sorry, this is not strictly on topic, but I just had GPT3 generate this response which I thought was really funny: > Write a satirical example of a Hacker News thread about a new service being released. User 1: Check out this new service
153.
by wizeman 4y ago
> Also Grover search does not work that way. I'm curious, what do you mean by this? Do you mean that Grover's algorithm can't speed up algorithms that use disk storage, or do you mean something else?
154.
by wizeman 4y ago
> > 256-bit ints > And now you're well over the border. Here's my plan. I'll wait a few decades until we have sufficiently-large and powerful quantum computers. Those reduce the time complexity from 2^256 to 2^128 ju
155.
by wizeman 4y ago
> No To be clear, you're saying that it wouldn't change the decidability, correct? > 0: Eg, the mass of the earth (in grams) is less than the mass of the moon (in grams) if you use 64-bit ints - but that's not true of
156.
by wizeman 4y ago
> The second Q needs no input because it is not executed: its source code is used as input for the first Q. But Q is the source code of a program that needs an input. How would you determine if Q halts or not, if you don't give it a
157.
by wizeman 4y ago
Also, I don't quite understand what the program QQ is. Q is a program that takes one input P. But then you said "QQ is a program which executes Q with itself as input". So in the program QQ, the first Q uses the second Q as i
158.
by wizeman 4y ago
The Tortoise and Hare algorithm is a generic Halting analyzer which works for all finite-state machines, it always halts, it always correctly tells you whether the input program halts or not (as long you give it enough memory), and it is li
159.
by wizeman 4y ago
> FOL + arithmetic is undecidable for reasons Kurt Godel discovered. Adding finite arithmetic (i.e. on N-bit words rather than mathematical integers) to FOL should not change the decidability of FOL, or does it?
160.
by wizeman 4y ago
Ok, for the sake of argument I will agree with you on "it's not practically useful" (for now, at least). But I will disagree with you on "it's not theoretically interesting". Almost the entire field of computer
161.
by wizeman 4y ago
> Well this one is just plain wrong. (...) Yes, the set of turing machines that halt in fewer than some fixed N steps is decidable. That is NOT the problem I mentioned. Programs that use a finite amount of memory do not necessarily halt,
162.
by wizeman 4y ago
Interesting, thank you! I am having a bit of difficulty understanding the exact implications in this context, but I will give it some thought.
163.
by wizeman 4y ago
As I said in my original post, Turing machines can be useful. But they do a huge simplifying assumption which is that the program can use an infinite amount of memory. This is OK in some cases, but it is not OK in others, especially when it
164.
by wizeman 4y ago
> When writing real systems, considering things like "oh well actually there is a stack depth limit" is zero help at best. That's not what I'm arguing at all. I'm arguing that as long as you restrict the programs
165.
by wizeman 4y ago
> Then we must differ on what the "halting problem" refers to. I would say that a computer suffers from the halting problem if there is no program it can run that can determine whether arbitrary programs it can run halt or not.
166.
by wizeman 4y ago
You are making an interesting argument but I am having a bit of difficulty in understanding it. So instead of saying: does program X with input X halt? You redefined the problem to be: does program X with input X halt within T time steps? T
167.
by wizeman 4y ago
> For your proposed example, a cycle detection program executed on a computer with finite memory cannot analyze all programs the computer can execute That is correct. A cycle detection program that can analyze all input programs with a m
168.
by wizeman 4y ago
> or by allowing it to exceed the resource bound. Exactly. When running A, in some cases you would necessarily need more memory to run it than the memory bound that you defined for the input program, if you want it to work for all input
169.
by wizeman 4y ago
> Ok, but unless you stick with some fixed resource limit N forever, the problem is undecidable again. Why do you believe that? The existence of the cycle detection algorithms that I mentioned earlier don't assume any particular num
170.
by wizeman 4y ago
> To be honest, I doubt that people who can actually make any progress in these areas would fail to know already what you are saying. I hope you are correct :-) > There are many results that show very weird consequences for having P=N
171.
by wizeman 4y ago
Yes, exactly, you seem to be understanding my point: there could be an efficient algorithm that can analyze any program with a bounded number of states and check that it halts. Among other things, because the P vs NP issue is still wide ope
172.
by wizeman 4y ago
> Of course they don’t, because it’s extremely obvious that it’s decidable for finite state machines. Wow, that's quite an interesting statement to make. And it doesn't explain dozens and dozens of statements that I've rea
173.
by wizeman 4y ago
> Things that are logically impossible on Turing machines appear to be effectively impossible on real computers, at least in the worst case. My problem is when Turing machines are used to justify something being true when it is actually
174.
by wizeman 4y ago
> It implies (rather, it’s just another way of saying) that no strictly correct algorithm can exist for detecting cycles on the state-space graphs of arbitrary Turing machines. Yes, what you said is strictly correct, but that's not
175.
by wizeman 4y ago
> By your definition, all problems of the form “does program X have property Y” are decidable, because you can just simulate X on all possible inputs until it halts or cycles, and observe whether Y holds in each case. Yes! Thank you! Tha
176.
by wizeman 4y ago
> GP wasn’t making a formal statement, so of course there isn’t. They were making an intuitive judgment about which of two mathematical theories corresponds more usefully to the real world. Ok, I see your points. > This is a non-sequi
177.
by wizeman 4y ago
> What I am saying is that in practice, for the huge majority of interesting problems, it is not useful to finitize the actual program but instead to abstract over the program that assumes no meaningful resource constraints. Wandering of
178.
by wizeman 4y ago
Agreed. Since the assumption has not been proven, this is why the foundation of cryptography is still on a bit of a shaky ground, as none of those algorithms are proven to be unbeatable (the one-time pad being the exception, although it&#x2
179.
by wizeman 4y ago
> Only an infinite number of subclasses of instances to go. There's only one subclass of instances for which the problem is undecidable: those where the program being analyzed is allowed to consume infinite memory. Which is not th
180.
by wizeman 4y ago
> In the real world, a program will either halt, loop, or crash, but this doesn’t help us if a 6 instruction program can take longer than the age of the universe to run while still terminating. No matter how fast you go through its state

More ›