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

71–80 of 196 posts

Re: What does “Undecidable” mean, anyway

#71

Post by ninkendo »

brap wrote: post #7

I sometimes wonder if the concept of “intelligence” is going to benefit from a formal model the way “computation” benefited from Turing Machines. Are there classes of intelligence? Are there things that some classes can and cannot do? Is it a spectrum? Is the set of classes countable? Is it finite? Is there a maximum intelligence? One can dream…

Kinda related, I’ve had a hunch for a while that we’re going to eventually learn that “the singularity” (AI’s improving themselves ad infinitum) is impossible for similar reasons the halting problem is impossible. I can’t really articulate why though. It just seems similarly naive to think “if the AI becomes smarter than us, surely it can thus make a better AI than we could” as it is to think “if a computer can compute anything, surely it can compute whether this program is will halt.”

My bet is there is some level of “incompleteness” to what an intelligence (ours or a machine’s) can do, and we can’t just assume that making one means it can become a singularity. More likely we’re just going to max out around human levels of intelligence, and we may never find a higher level than that.

Re: What does “Undecidable” mean, anyway

#72

Post by graycat »

> What does “Undecidable” mean, anyway

A big and relatively recent example is to take (1) the axioms of Zermelo-Fraenkel set theory and (2) the axiom of choice and ask if (1) can be used to prove or disprove (2). The surprising answer is "No", i.e., (1) cannot be used either to prove or disprove (2). So, can work with (1) and, whenever convenient, assume (2), continue on, and never encounter a problem.

So, given (1), (2) is undecidable.

The work was by Paul J. Cohen as at

https://en.wikipedia.org/wiki/Paul_Cohen

The field of research about what is undecidable also goes back to Kurt Gödel as at

https://en.wikipedia.org/wiki/Kurt_G%C3%B6del

Another example, starting with (1), of an undecidable statement is the continuum hypothesis:

     There is no set whose cardinality is
     strictly between that of the integers
     and the real numbers.
In simple terms, "cardinality" means that there is no set X that is too large to be put into 1-1 correspondence with the set of integers and too small to be put into 1-1 correspondence with the set of real numbers.

Re: What does “Undecidable” mean, anyway

#73

Post by Animats »

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 it's important.

Re: What does “Undecidable” mean, anyway

#74

Post by cyberax »

mreid wrote: post #65

This is a really nice explanation of decidability. One extra thing it might be worth mentioning is that there are many more functions `f : string -> boolean` then there are programs that implement those functions. When I first encountered this topic I had trouble intuitively understanding how there could not exist an `IS_HALTING` function when it is also just a function that takes in a string (representing a program…

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.

Re: What does “Undecidable” mean, anyway

#75

Post by pixl97 »

ninkendo wrote: post #71
brap wrote: post #7

I sometimes wonder if the concept of “intelligence” is going to benefit from a formal model the way “computation” benefited from Turing Machines. Are there classes of intelligence? Are there things that some classes can and cannot do? Is it a spectrum? Is the set of classes countable? Is it finite? Is there a maximum intelligence? One can dream…

Kinda related, I’ve had a hunch for a while that we’re going to eventually learn that “the singularity” (AI’s improving themselves ad infinitum) is impossible for similar reasons the halting problem is impossible. I can’t really articulate why though. It just seems similarly naive to think “if the AI becomes smarter than us, surely it can thus make a better AI than we could” as it is to think “if a computer can compu…

>More likely we’re just going to max out around human levels of intelligence, and we may never find a higher level than that.

I've seen people state this before, but I don't think I've seen anyone make a scientific statement on why this could be the case. The human body has a rather tight power and cooling envelope itself. On top of that we'd have to ask how and why our neural algorithm somehow found the global maxima of intelligence when we can see that other animals can have higher local maxima of sensory processing.

Moreso machine intelligence has more exploration room to search the problem space of survival (aka Mickey7) that the death any attached sensoring/external network isn't the death of the AI itself. How does 'restore from backup' affect the evolution of intelligence?

Granted there are limits somewhere, and maybe those limits are just a few times what a human can do. Traversing the problem space in networks much larger than human sized capabilities might explode in time and memory complexity, or something weird like that.

Re: What does “Undecidable” mean, anyway

#76

Post by hwayne »

cyberax wrote: post #74
mreid wrote: post #65

This is a really nice explanation of decidability. One extra thing it might be worth mentioning is that there are many more functions `f : string -> boolean` then there are programs that implement those functions. When I first encountered this topic I had trouble intuitively understanding how there could not exist an `IS_HALTING` function when it is also just a function that takes in a string (representing a program…

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.

`S = {str -> bool}` is actually uncountable. `S` is isomorphic to the power set (set of all subsets) of `str`, and `2^str` is at least as big as the set of real numbers, as any real number (like π) can be mapped to the set of string prefixes (like `{"3", "3.1", "3.14", ...}`). Since the reals are uncountable, so is `2^str` and `S`.

Re: What does “Undecidable” mean, anyway

#77

Post by nitwit005 »

skydhash wrote: post #57
nitwit005 wrote: post #42

Earlier quoted context omitted.

I have to vote the opposite direction. I don't think it's ever been relevant. As an example, A practical walk through of what a simple CPU is doing was quite useful for getting the idea of what's going on. The concept of a Turing machine, which was originally intended for mathematical proofs, was not.

The CPU is an implementation of theory. It just happens that the realization of several axioms in the Turing machine is realizable physically. And the rest hold true. The nice thing with notation is that they're more flexible than building/creating/executing the thing they describe.

If you look back at the history, CPUs were often designed for specific tasks, and some of the early ones lacked conditional jumps that you'd normally consider nessesary for a Turing machine.

We've made them more general purpose as that sells better, not because people cared about making Turing machines.

Re: What does “Undecidable” mean, anyway

#78

Post by Aziell »

The first time I encountered the halting problem, I was honestly confused. I kept thinking there had to be another solution. But over time, I came to realize it wasn’t a technical issue ,it was about the limits of computation itself. This article explains the concept of undecidability really well. It breaks things down in a very practical way. That last part, about the limits of how we think, really hit me.

Re: What does “Undecidable” mean, anyway

#79

Post by ummonk »

"This to me is a strong "intuitive" argument for why the halting problem is undecidable: 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."

I don't buy this. Bcrypt cracking and solving chess is easy already if you don't care about runtime complexity (both have rather trivial finite -- albeit exponential -- runtime algorithms), and it wouldn't be any easier to transform them into halting problems.

Re: What does “Undecidable” mean, anyway

#80

Post by ummonk »

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…

Yes, the article is clearly confused about the concepts, given its mention of bcrypt cracking and chess engines.
Post reply on HN