News for hackers. Stuff that matters.
Re:The Halting Problem Is Decidable on a Set of Asymptotic P... by jameshart on Sunday May 28, 2023 @02:55PM (#36106706)
Similarly, as the number of particles in a system increases, the less you have to worry about Heisenberg uncertainty bounds on your momentum/position measurements.

It’s a misreading of the halting problem to think of it as a ‘barrier’ of some sort. What it really means is that there are some computer programs where the only way to find out what they will do is to actually run them. There’s not a ‘better trick’ you can pull to get the answer. This is kind of intuitive, since we know there are problems we run into where the easiest way we can think of to solve them is to write a program and run it. The halting problem tells us that it’s plausible that that instinct is right - that for some programs, you really can’t do some other analysis of the program that tells you what it’s going to do. You have to just run it.

Like: take a random complex number with magnitude < 2. Keep squaring it and adding the original number. Will you ever get a number with magnitude > 2?

For some numbers you can take a shortcut and say yes or no. But for others the only way to find out is to keep doing it.

Re:The Halting Problem Is Decidable on a Set of Asymptotic P... by mgraczyk on Sunday May 28, 2023 @03:38PM (#36107043)
> The halting problem tells us that it’s plausible that that instinct is right - that for some programs, you really can’t do some other analysis of the program that tells you what it’s going to do. You have to just run it.

This isn't quite right. The halting problem says that you can't just run it. If you just run it, you will not learn whether or not it halts after any finite amount of time.

Also I don't see how this is related to uncertainty bounds.

Re:The Halting Problem Is Decidable on a Set of Asymptotic P... by ttctciyf on Sunday May 28, 2023 @04:27PM (#36107451)
> If you just run it, you will not learn whether or not it halts after any finite amount of time.

If it halts within a finite amount of time, you will.

Re:The Halting Problem Is Decidable on a Set of Asymptotic P... by amelius on Sunday May 28, 2023 @06:31PM (#36108416)
But that is not the only possibility. So you are missing the point.
Re:The Halting Problem Is Decidable on a Set of Asymptotic P... by Sinidir on Sunday May 28, 2023 @07:45PM (#36108932)
They are not missing the point. The previous post was simply wrong. The halting problem is semi-decidable. So you can potentially find out wether a program halts.
Re:The Halting Problem Is Decidable on a Set of Asymptotic P... by amelius on Sunday May 28, 2023 @07:58PM (#36109020)
Besides missing the point, this is also pedantic and quite boring.
Re:The Halting Problem Is Decidable on a Set of Asymptotic P... by SideQuark on Sunday May 28, 2023 @10:19PM (#36109871)
No you won't. Pick any finite time you will check. It may not stop by then, yet may stop later. So ahead of time, even if the program will stop, you cannot make a plan to learn that in finite time. You're stuck letting run possibly forever, because at each finite time you still cannot answer yes or no. Only if you've waited long enough, which can be arbitrarily far out, and it stops, can you answer.
Re:The Halting Problem Is Decidable on a Set of Asymptotic P... by ttctciyf on Monday May 29, 2023 @01:44AM (#36111052)
> Only if you've waited long enough, which can be arbitrarily far out, and it stops, can you answer

So, we agree!

Re:The Halting Problem Is Decidable on a Set of Asymptotic P... by simiones on Monday May 29, 2023 @05:44AM (#36112331)
Well, it depends how you take it. The fact that the halting problem is undecidable tells us that there is no algorithm to tell if an algorithm will ever halt for some input. This implies that the best we can do if we want to find out if an arbitrary algorithm A will halt for some input B is to run A with input B. We may still never find out, but we also have no better way.
Re:The Halting Problem Is Decidable on a Set of Asymptotic P... by Y_Y on Sunday May 28, 2023 @03:10PM (#36106829)
What does this have to do with Heisenberg uncertainty?
Re:The Halting Problem Is Decidable on a Set of Asymptotic P... by qubex on Sunday May 28, 2023 @04:09PM (#36107287)
I think you’re confusing computational irreducibility and the halting problem.
Re:The Halting Problem Is Decidable on a Set of Asymptotic P... by s-zeng on Sunday May 28, 2023 @07:13PM (#36108723)
I think he might be referring to Rice's Theorem, which to be fair is reducible to the halting problem
Re:The Halting Problem Is Decidable on a Set of Asymptotic P... by simiones on Monday May 29, 2023 @05:46AM (#36112341)
Computational irreducibility is one consequence of the halting problem being undecidable. If the halting problem were decidable, there couldn't be any computationally irreducible algorithms.
Re:The Halting Problem Is Decidable on a Set of Asymptotic P... by jameshart on Monday May 29, 2023 @09:48AM (#36113918)
Right, these things are all corollaries of one another.
Re:The Halting Problem Is Decidable on a Set of Asymptotic P... by saghm on Sunday May 28, 2023 @05:10PM (#36107813)
> Similarly, as the number of particles in a system increases, the less you have to worry about Heisenberg uncertainty bounds on your momentum/position measurements.

This certainly makes intuitive sense, since it explains why we don't have trouble measuring both the speed and position of objects in everyday life with fairly high precision.

Re:The Halting Problem Is Decidable on a Set of Asymptotic P... by teaearlgraycold on Sunday May 28, 2023 @05:49PM (#36108131)
Unexpected Mandelbrot
Re:The Halting Problem Is Decidable on a Set of Asymptotic P... by simiones on Monday May 29, 2023 @05:39AM (#36112300)
> Similarly, as the number of particles in a system increases, the less you have to worry about Heisenberg uncertainty bounds on your momentum/position measurements.

I don't think this is correct. In fact, in certain systems, the Heisenberg uncertainty can get amplified as the number of particles increases - which is why we end up needing the addition of the Born rule in QM to predict classical observations, and can't just deduce them from the base equations. And also why we end up predicting a particle can go either left with some probability or right with one minus that probability, instead of being able to say "that particle will go right".

Re:The Halting Problem Is Decidable on a Set of Asymptotic P... by jameshart on Monday May 29, 2023 @09:47AM (#36113913)
Yet you can generally catch a thrown ball.

The point of the analogy was that the halting problem - like the uncertainty principle - is a result that says that you can’t know certain things about systems - and with small systems in particular figuring that out can be as complex as the system itself. But they don’t prevent us from doing useful things with larger systems. It struck me as a similar result to this paper - though only by analogy, not like, in some deep way.

Re:The Halting Problem Is Decidable on a Set of Asymptotic P... by tsimionescu on Monday May 29, 2023 @12:45PM (#36115566)
My point was more that Heisenberg uncertainty doesn't simply go away because of the size of the system, it is explicitly not an element of classical physics. If you apply the equations of QM to a system of any size, you'll see compounding uncertainty, not an attenuation.

The fact that classical objects have deterministic trajectories is not a consequence of statistics + Heisenberg uncertainty, it is explicitly in contradiction to Heisenberg uncertainty, requiring an extra element to be added to the theory (the Born rule).