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

51–60 of 196 posts

Re: What does “Undecidable” mean, anyway

#51

Post by bawolff »

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…

> Is ChatGPT on par with a human child? A smart dog? Crows? A college professor? PhD level?

That presumes a total ordering of intelligence. I think the balance of evidence is that no such total ordering exists.

There are things chatgpt can do that children (or adults) cannot. There are thing that children can do that chatgpt cannot.

At best maybe the Turing test can give us a partial ordering.

I don't think there is much value in viewing "intelligence" as a whole. Its a combination of a multitude of factors, that need to be dealt with independently.

Re: What does “Undecidable” mean, anyway

#52

Post by tel »

cubefox wrote: post #15

There are at least two meanings of "undecidable". The one, from computer science, is discussed in the blog post. The other, from formal logic, is a synonym to "independent". A proposition (not property) is independent of some axiomatic theory with respect to a proof system, if and only if the proposition can neither be proved nor disproved in that theory. For example, the continuum hypothesis is independent of ZFC. A…

Independent and undecidable aren't quite the same, even in formal logic. Or rather, sometimes they are but it’s worth being specific.

A proposition P being independent of a theory T means that both (T and P) and (T and not P) are consistent. T has nothing to say about P. This may very well be what Gödel was indicating in his paper.

On the other hand, undecidable has a sharper meaning in computation contexts as well as constructive logics without excluded middle. In these cases we can comprehend the “reachability” of propositions. A proposition is not true or false, but may instead be “constructively true”, “constructively false”, or “undecidable”.

So in a formal logic without excluded middle we have a new, more specific way of discussing undecidability. And this turns out to correspond to the computation idea, too.

Re: What does “Undecidable” mean, anyway

#53

Post by skydhash »

Aicy wrote: post #40
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

It's the recursive nature of it.

Almost any program can be written in a DSL that solves the class of problem that the program solves. So if you consider the user stories of your project as that class of problem, you can come up with with a DSL (mostly in form of pseudocode) that can describe the solution. But first you need to refine the terms down to some primitives (context free grammar). You then need to think about the implementation of the execution machine. which will be a graph of states (automata). The transition between the states will be driven by an execution machine. The latter needs not be as basic as the Turing machine.

But often, you do not need to do all these stuff. You can just use common abstractions like design patterns, data structures, and basic algorithms to have a ready made solution. But you still have to compose them and if you understand how everything works, it's easier to do so.

Re: What does “Undecidable” mean, anyway

#55

Post by [deleted] »

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…

[deleted]

Re: What does “Undecidable” mean, anyway

#57

Post by skydhash »

nitwit005 wrote: post #42
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…

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.

Re: What does “Undecidable” mean, anyway

#58

Post by [deleted] »

wat10000 wrote: post #46
ryandamm wrote: post #10

Earlier quoted context omitted.

Purely intuitively, it seems like there should be a connection between the two (computation and intelligence). But I have not formally studied any relevant fields, I would be interested to hear thoughts from those who have.

The known laws of physics are computable, so if you believe that human intelligence is purely physical (and the known laws of physics are sufficient to explain it) then that means that human intelligence is in principle no more powerful than a Turing machine, since the Turing machine can emulate human intelligence by simulating physics. If there's a nonphysical aspect to human intelligence and it's not computable, th…

[deleted]

Re: What does “Undecidable” mean, anyway

#60

Post by kazinator »

mrkeen wrote: post #35
cubefox wrote: post #16

Earlier quoted context omitted.

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 algorit…

If statement S1 halts and we combine it with S2 like "S1; S2", then we know that halts. :)
Post reply on HN