Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

What does “Undecidable” mean, anyway

buttondown.com

Post reply on HN
Print view View original

101–110 of 196 posts

Re: What does “Undecidable” mean, anyway

#101

Post by Dylan16807 »

jonahx wrote: post #95
Dylan16807 wrote: post #90

Earlier quoted context omitted.

> "Free" in the sense of thought, cleverness, insight. You have an "everything" calculator. That is the sense in which it might be intuitive that it couldn't exist. Right. But brute force solvers for bcrypt and chess are already "free" in the sense of thought, cleverness, insight. We already have the "everything" algorithm: iterate through all possible solutions in O(2^n) time and pick the best one. A halting solver…

Yeah, I thought I already addressed that above. Can we do the same for a theorem prover? For proofs of some fixed finite length, I think the answer is yes, but without that constraint the answer is no. Whereas with a halting detector we could. It still seems to me your complaint (and the other poster's) are just about these specific examples rather than general argument Hillel is making. Please clarify if that's not…

The problem is the author's giving a misleading picture of the problem space with those examples.

Tasks like optimizing whole programs or running a theorem prover are difficult/impossible tasks to do perfectly. We don't have a solution verifier that we can plug into the "free" brute force framework. With theorem provers, even when restricted to fixed finite (non-trivial) lengths, I don't think we have one that always gives the right answer. And fully optimizing programs is similarly impossible to be perfect at. But if you had a halting solver you could bypass those difficulties for all of those problems.

Tasks like breaking encryption or playing chess have super simple verifiers. A halting solver would solve them sure, but we already have programs to solve them. We only lack fast enough computer to run those programs.

These are both big and significant classes of problem. The latter is not just a couple scattered examples. It has its own answers to the important questions like whether you can try every answer to make an "everything" calculator. For the first class you can't, for the second class you can. The intuition that such a thing is "too powerful" is actually a pretty bad intuition here.

Re: What does “Undecidable” mean, anyway

#102

Post by yusina »

Animats wrote: post #73

Any deterministic system with a finite number of states is decidable, in the halting problem sense. Either it halts or repeats a state. The halting problem only applies for infinite memory. Now, there are finite state systems where the halting problem is arbitrarily hard. But that's not undecidability. That's complexity. That's a problem in the space where P=NP lives. The article does not make this distinction, and i…

The halting problem applies also for finite-but-unbounded memory.

If you give me a decider that can tell me for any program with a state space up to size N whether it halts or not, then I will be able to produce another program with a larger state space and which then your decider won't be able to decide. This new program doesn't use infinite space. Just more than your decider can handle. You can't produce a single decider that works for all inputs.

It is often ok to approximate "finite but unbounded" with "infinite", and surely anyhing that can handle infinite inputs will be able to handle finite-but-unbounded inputs too, but in this context the two are not the same.

The term "infinite" is often misused to mean "finite but unbounded" but it is an important distinction.

Re: What does “Undecidable” mean, anyway

#103

Post by drewhk »

mreid wrote: post #88
cyberax wrote: post #74

Earlier quoted context omitted.

I wonder if this is a correct argument. A function string -> boolean is always expressible? Simply because the set of all possible mappings from all possible finite strings to booleans is countable. It's better to say that some functions like "does this program halt?" simply don't exist.

I think you are experiencing the same confusion I felt when I first started thinking about the difference between a program and a function. The set of all possible mapping from all possible finite strings to booleans is definitely *not* countable. What I (and the article) mean by a "function" `f : string -> boolean` here is any arbitrary assignment of a single boolean value to every possible string. Let's consider tw…

> The set of all possible mapping from all possible finite strings to booleans is definitely not countable.

Just to add another perspective to this, this is one of the places where classical and constructive mathematics diverge. Do those functions that are not expressible by algorithms (algorithms are countable) even exist? Of course you can define them into existence, but what does that mean?

Another food for thought is to consider if the limits imposed on computation by the Turing machine is a law of physics? Is this an actual physical limit? If so, what does that mean about the functions not expressible by algorithms? What is so exciting about programs/algorithms that they are both a well-defined mathematical object suitable for formal analysis, but they are actually machines as well, fully realizable physically and their properties physically falsifiable.

Before anyone starting to nit-pick, I just put this comment here as a conversation starter, not a precise thought-train: this is a deep rabbit whole that I think is worth to explore for everyone interested in the computational world. I am pretty sure other commenters can add more accurate details!

Re: What does “Undecidable” mean, anyway

#104

Post by mreid »

yusina wrote: post #98
mreid wrote: post #88

Earlier quoted context omitted.

I think you are experiencing the same confusion I felt when I first started thinking about the difference between a program and a function. The set of all possible mapping from all possible finite strings to booleans is definitely *not* countable. What I (and the article) mean by a "function" `f : string -> boolean` here is any arbitrary assignment of a single boolean value to every possible string. Let's consider tw…

I appreciate your lengthy explanation and I largely agree with it, even though it probably doesn't help much because anybody who has not understood this yet will have stopped reading latest at 20% in. That's not your fault but just based on the observation that attention spans are short and people strongly prefer to spend their time on reading things they are interested in. And anybody interested in this subject who…

Sure, “arbitrary” is a suitable term here too. A random process is just one way to generate an arbitrary function.

My use of “random” here was referring to the coin flipping process and was more for building intuition than precisely specifying all the other non-expressible functions. I was trying to allude to the fact that these other type of functions don’t have any easily expressible process behind them. When I’ve taught this stuff in the past I’ve found that people latch onto coin flipping more easily that imagining some arbitrary assignment of values.

For what it’s worth, I used to be a researcher in probability and information theory and have published papers on those topics so I am aware of the various technical definitions of randomness (Kolmogorov axioms, algorithmic probability theory, etc.)

I think you’re right about my comment being a little too lengthy for most people to find useful. I started explaining this stuff and got carried away.

Re: What does “Undecidable” mean, anyway

#105

Post by dmurray »

bubblyworld wrote: post #100
dmurray wrote: post #97

Earlier quoted context omitted.

Yes, I thought the article was really good until it got to that point. > a halt detector can be trivially repurposed as a program optimizer / theorem-prover / bcrypt cracker / chess engine. It's too powerful, so we should expect it to be impossible.) A Turing machine can be trivially repurposed as a bcrypt cracker or chess engine (for the same definition of trivial the author is using), so if it's not intuitive that…

A solution to the Halting problem can be repurposed as a general-purpose theorem prover. The author is correct. You simply write a program that searches all possible valid proofs till it finds the one you are looking for (or maybe doesn't and runs forever). Then you check whether it halts with your Halting solution - if that returns true, you know that a proof exists, otherwise you know that one doesn't. In other wor…

I edited the last part; I meant that the Turing machine from my second paragraph can't do those things, though the Halting machine can.

Re: What does “Undecidable” mean, anyway

#106

Post by mreid »

drewhk wrote: post #103
mreid wrote: post #88

Earlier quoted context omitted.

I think you are experiencing the same confusion I felt when I first started thinking about the difference between a program and a function. The set of all possible mapping from all possible finite strings to booleans is definitely *not* countable. What I (and the article) mean by a "function" `f : string -> boolean` here is any arbitrary assignment of a single boolean value to every possible string. Let's consider tw…

> The set of all possible mapping from all possible finite strings to booleans is definitely not countable. Just to add another perspective to this, this is one of the places where classical and constructive mathematics diverge. Do those functions that are not expressible by algorithms (algorithms are countable) even exist? Of course you can define them into existence, but what does that mean? Another food for though…

These are definitely thought-provoking questions and there are branches of mathematical philosophy such as constructivism and mathematical intuitionism that explore these.

Even if computation is not directly part of the laws of physics, knowing that humans and our computers are limited to things that are finite and computable might place limits on how we can appreciate how the universe works.

This is kind of a digression but if you (or others) are interested in some examples of things that are right on the edge of these questions you should check out the [busy beaver function](https://www.quantamagazine.org/amateur-mathematicians-find-f...). This tell you the maximum number of steps an n-state Turing machine can take before halting.

Re: What does “Undecidable” mean, anyway

#107

Post by bubblyworld »

dmurray wrote: post #105
bubblyworld wrote: post #100

Earlier quoted context omitted.

A solution to the Halting problem can be repurposed as a general-purpose theorem prover. The author is correct. You simply write a program that searches all possible valid proofs till it finds the one you are looking for (or maybe doesn't and runs forever). Then you check whether it halts with your Halting solution - if that returns true, you know that a proof exists, otherwise you know that one doesn't. In other wor…

I edited the last part; I meant that the Turing machine from my second paragraph can't do those things, though the Halting machine can.

Right, yeah that makes sense. But I think the author understands that very well.

Re: What does “Undecidable” mean, anyway

#108

Post by dmurray »

bubblyworld wrote: post #107
dmurray wrote: post #105

Earlier quoted context omitted.

I edited the last part; I meant that the Turing machine from my second paragraph can't do those things, though the Halting machine can.

Right, yeah that makes sense. But I think the author understands that very well.

Of course he must. But the fact that we're arguing about it (and there's another thread with the same conversation) says that at least, the intent of this part wasn't clear.

Re: What does “Undecidable” mean, anyway

#109

Post by jonahx »

ummonk wrote: post #99
jonahx wrote: post #95

Earlier quoted context omitted.

Yeah, I thought I already addressed that above. Can we do the same for a theorem prover? For proofs of some fixed finite length, I think the answer is yes, but without that constraint the answer is no. Whereas with a halting detector we could. It still seems to me your complaint (and the other poster's) are just about these specific examples rather than general argument Hillel is making. Please clarify if that's not…

The complaint is that Hillel is providing an intuitive explanation but that intuition is clearly faulty, as demonstrated by two of the examples he gave. P.S., you can run that proof finding algorithm (iterate through every candidate proof one by one and check for validity) for proofs of finite length in general, not just some fixed finite length. Where the halting oracle comes in is that you can use it to check wheth…

> for proofs of finite length in general, not just some fixed finite length.

For a brute force proof finder, for your program to be guaranteed to finish in theory, you have to pick a length. So it is fixed. Ofc you can choose whatever length you want. But you don't have that constraint with the halting oracle. Perhaps we're saying the same thing?

Re: What does “Undecidable” mean, anyway

#110

Post by drewhk »

mreid wrote: post #106
drewhk wrote: post #103

Earlier quoted context omitted.

> The set of all possible mapping from all possible finite strings to booleans is definitely not countable. Just to add another perspective to this, this is one of the places where classical and constructive mathematics diverge. Do those functions that are not expressible by algorithms (algorithms are countable) even exist? Of course you can define them into existence, but what does that mean? Another food for though…

These are definitely thought-provoking questions and there are branches of mathematical philosophy such as constructivism and mathematical intuitionism that explore these. Even if computation is not directly part of the laws of physics, knowing that humans and our computers are limited to things that are finite and computable might place limits on how we can appreciate how the universe works. This is kind of a digres…

It is also interesting to consider, that if all transcendental numbers exist physically, then it basically means that there is an experiment that yields the Nth digit of such a number (for any N assuming unlimited physical resources to realize the experiment). If such experiment does NOT exist though, then there cannot be any relevance physically of that Nth digit (otherwise the "relevance" would materialize as an observable physical effect - an experiment!). This is something Turing machines cannot do for uncomputable numbers, like Chaitin's Omega, etc. We can yield the Nth digit of _many_ transcendental numbers (PI, e, trig functions, etc), but not all of them. It is so interesting that physics, machines and the existence of all the real numbers are so intertwined!

Of course one can also ponder, even if a mathematical object is "un-physical", can it be still useful? Like negative frequencies in fourier analysis, non-real solutions to differential equations, etc. Under what conditions can "un-physical" numbers be still useful? How does this relate to physical observation?

And just for the fun of it: when you execute unit tests, you are actually performing physical experiments, trying to falsify your "theory" (program) :D

Post reply on HN