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

31–40 of 196 posts

Re: What does “Undecidable” mean, anyway

#31

Post by joe_the_user »

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…

I agree the idea of a formal view of intelligence is appealing. The hurdle that any such view faces is that most intelligence seems to involve rough, approximate reasoning.

I think this approximate nature of intelligence is essentially why neural nets have been more successful than earlier Gofai/logic based system. But I don't think that means formal approaches to intelligence are impossible, just they face challenges.

Re: What does “Undecidable” mean, anyway

#32

Post by taeric »

I'm curious if you could make an analogy to the idea of "underspecified" in FreeCAD. It isn't that the drawing doesn't exist. It is that you still have some freedom in how long certain parts could be. Crucially, not all. It could be that parts of the drawing are indeed fully specified.

Same can go with programs. You can constrain parts of it enough that you can answer some pretty specific questions. And similar to how a drawing with fewer lines is easier to constrain, a program that has restricted constructs can be easier to constrain.

Re: What does “Undecidable” mean, anyway

#33

Post by joe_the_user »

bawolff wrote: post #22
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…

Philosophers have been trying to define what it means to be conscious since forever. I think that is informally what you mean here. If you just mean what problems can it solve, and how quickly, we already have a well developed theory of that in terms of complexity classes - https://complexityzoo.net/Complexity_Zoo

I don't either philosophical conceptions of consciousness or theories of computational complexity count as even "efforts to formalize intelligence". They are each focused on something significantly different.

The closest effort I know of as far characterizing intelligence as such is Steven Smale's 18th problem.

https://en.wikipedia.org/wiki/Smale%27s_problems

Re: What does “Undecidable” mean, anyway

#34

Post by mystified5016 »

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…

This is one of those ideas that great minds have been chewing on for all of recorded history.

In modern thinking, we do certainly recognize different classes of intelligence. Emotional intelligence, spatial reasoning, math, language, music.

I'd say the classes of intelligence are finite. Primarily because different types of intelligence (generally) rely on distinct parts of our finite brains.

As for maximum intelligence, I like the angle taken by several SciFi authors. Generally, when an AI is elevated to the extremes of intelligence, they detach from reality and devolve into infinite naval gazing. Building simulated realities or forever lost in pondering some cosmic mystery. Humans brought to this state usually just die.

For physical, finite entities, there's almost certainly an upper limit. It's probably a lot higher than we think, though. Biological entities have hard limits on energy, nutrients, and physical size beyond which it's just impossible to maintain any organism. Infinities are rarely compatible with biology, and we will always be limited.

Even an AI is still beholden to the practicalities of moving energy and resources around. Your processor can only get so large and energy/information can only move so fast. Intelligence in AI is probably also bounded by physical constraints, same as biological entities.

Re: What does “Undecidable” mean, anyway

#35

Post by mrkeen »

cubefox wrote: post #16
kazinator wrote: post #11

An undecidable problem in the Turing computational model is this: it is a problem for which no algorithm exists which can ] decide every input case . This doesn't preclude some input cases from being decided. What happens it that every attempt at making an algorithm for an undecidable problem will run into two issues: there will be input cases for which an answer exists, but for which the algorithm either gets into a…

Do you know whether there is an algorithm which "mostly" solves the halting problem, by returning either "halts", "doesn't halt" or "don't know", while only very rarely returning "don't know" for (what we would intuitively consider) natural algorithms?

I think it would be much more fruitful to flip it around the other way.

Start with small pieces which halt, and see how far you can get by combining them into larger programs. Compiler-help is available: https://docs.idris-lang.org/en/latest/tutorial/theorems.html...

A down-side of a yes/no/maybe halting checker is that it wouldn't tell you why. You'd get your "doesn't halt" result and then have to debug the algorithm.

Re: What does “Undecidable” mean, anyway

#36

Post by skydhash »

mystified5016 wrote: post #27
bawolff wrote: post #22

Earlier quoted context omitted.

Philosophers have been trying to define what it means to be conscious since forever. I think that is informally what you mean here. If you just mean what problems can it solve, and how quickly, we already have a well developed theory of that in terms of complexity classes - https://complexityzoo.net/Complexity_Zoo

I think this is more about levels or classifications of intelligence. If you've ever interacted with a very smart animal, it's easy to recognize that their reasoning abilities are on par with a human child in a very subjective and vague way. We can also say with extreme confidence that humans have wildly different levels of intelligence and intellectual ability. The question is, how do we define what we mean by "Alic…

Intelligence is often a measure how quickly we can embrace a new model and how effectively we can use it. Building such a model can be done haphazardly or be guided with skill transfer methodology. Once that done, intelligence is how well we can select the correct model, filter the relevant parameters out and then produce a correct answer.

There's a lot of factors there and more that I haven't specified. But one thing that I believe is essential is the belief that an answer is correct or uncertain.

Re: What does “Undecidable” mean, anyway

#37

Post by constantcrying »

taeric wrote: post #32

I'm curious if you could make an analogy to the idea of "underspecified" in FreeCAD. It isn't that the drawing doesn't exist. It is that you still have some freedom in how long certain parts could be. Crucially, not all. It could be that parts of the drawing are indeed fully specified. Same can go with programs. You can constrain parts of it enough that you can answer some pretty specific questions. And similar to ho…

>I'm curious if you could make an analogy to the idea of "underspecified" in FreeCAD.

That is just solution theory of a non-linear system of equations. The solution space can have exactly one solution (fully constrained), more than one (under constrained) or zero (over constrained).

To be honest I do not really see a connection.

Re: What does “Undecidable” mean, anyway

#40

Post by Aicy »

skydhash wrote: post #2

One of the biggest boost to my SWE career was studying theory of computation and programming languages theory. My major was electronic engineering, so I didn't touch those at the university. But I use some books to at least grasp the introductory knowledge. The boost was how easy it is to find the mechanism to some abstractions. And instead of being those amazing and complex tools that you have to use carefully, they…

Really? I studied it in my undergrad degree, and since then have worked as a SWE and not found it relevant at all really
Post reply on HN