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

131–140 of 196 posts

Re: What does “Undecidable” mean, anyway

#131

Post by skydhash »

andoando wrote: post #113
Dylan16807 wrote: post #94

Earlier quoted context omitted.

If the only principle you look at is "does this compute?" then they're not that different. Otherwise they're about as far apart as you can get. A Turing machine (at least one that isn't designed in some super wacky way to prove a point) has a few bits of internal state and no random access memory. If you want RAM you have to build a virtual machine on top of the Turing machine. If you try to program it directly it's…

Turing machine in essence is a finite state machine + memory (the tape) + some basic instructions for reading and writing to the memory. Its a very simple, rudimentary computer, not some completely abstract mathematical object, which was what I was responding to. With universal turing machines, its not difficult to start writing composable functions, like an assembly instruction set, adders, multipliers, etc. TMs cer…

One realization with TM is that programs and data are essentially the same and separation is usually imposed. When you think about your program as data, it’s hard to not notice patterns and you start to yearn for metaprogramming to more expressively express those.

Re: What does “Undecidable” mean, anyway

#132

Post by ComplexSystems »

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…

My complaint is that I don't get what we are getting at when we reference "creativity," "cleverness," "ingenuity" and so on. The halting problem cannot be solved, in the general case, by any machine constructable in physical reality. That includes both computers and human beings. And computers can keep at it much longer than I can, come up with novel hypotheses to test much longer than I have the patience for, and can basically do anything I can do except try a bunch of random crap out of sheer frustration and eventually give up.

Re: What does “Undecidable” mean, anyway

#133

Post by Xcelerate »

Ukv wrote: post #121
bubblyworld wrote: post #96

Earlier quoted context omitted.

I don't think this is an important distinction. The point of Turing machines is that you can ask questions like "can all instances of this problem be solved uniformly, and how relatively expensive is it?". This requires infinite memory in a formal sense , because instances of (most) problems can be arbitrarily large. Yes, if you ask the same question with a fixed (finite) memory restriction on everything, the answer…

> Yes, if you ask the same question with a fixed (finite) memory restriction on everything, the answer is uninteresting. To me, this is... uninteresting. It tells you nothing about the underlying logical structure of your problem, which is what mathematicians are really trying to get at! > (first and foremost Turing machines are a tool for analysing problems mathematically, not a model of your laptop) I think what ma…

To be fair to [0], Leonid Levin (co-discoverer of NP-completeness) makes a similar but slightly weaker claim in a more formal sense: that no algorithm or even random process can increase mutual algorithmic information between two strings (beyond O(1)), which includes any process that attempts to increase mutual information with the halting sequence (https://cs-web.bu.edu/fac/lnd/dvi/IIjacm.pdf).

Nevertheless, we clearly do have some finite amount of information about this sequence, evident in the axioms of PA or ZFC or any other formal system that proves an infinite number of programs as non-halting (hence why the Busy Beaver project has been able to provably confirm BB(5)). We presume these systems are truly consistent and sound even if that fact is itself unprovable, so then where exactly did the non-halting information in the axioms of these systems “come from”?

Levin stops short of speculating about that, simply leaving it at the fact that what we have so far cannot be extended further by either algorithmic or random means. But if that’s the case, then either AI is capped at these same predictive limits as well (i.e., in the sense of problems AI could solve that humans could not, both given unlimited resources), or there is additional non-halting information embedded in the environment that an AI could “extract” better than a human. (I suppose it’s also possible we haven’t fully exploited the non-halting information we do have, but I think that’s unlikely since we’re not even sure whether BB(6) is ZFC-provable and that’s a rather tiny machine).

Re: What does “Undecidable” mean, anyway

#134

Post by LPisGood »

yusina wrote: post #102
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 d…

I don’t think finite-but-unbounded and infinite makes any difference in this setting, since at most finitely many cells of the memory tape may be used at any stage of computation.

Re: What does “Undecidable” mean, anyway

#136

Post by LPisGood »

gnulinux wrote: post #3

The reason decidability makes no or very little sense to tons of CS or Math majors is because the logical basis of decidability is almost never explained in school. Even if you're in a logic/computability class you likely won't get a very concrete explanation, unless you're in a Philosophy of Math class. The problem that's usually not told to kids is that decidability has different sort of implications to classical m…

I was with you until here:

> which is how you would postulate it in homotopy type theory: https://agda.github.io/agda-stdlib/master/Axiom.ExcludedMidd...

Why did you randomly shoehorn in homotopy type theory? Maybe I’m overreacting to this, but the only person I’ve ever known to shoehorn homotopy type theory into largely unrelated discussion has left quite a poor impression for me.

Re: What does “Undecidable” mean, anyway

#137

Post by tel »

alok-g wrote: post #89
tel wrote: post #52

Earlier quoted context omitted.

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

Could I say that 'P is Undecidable' is defined as: It is False that {There exists T such that [(T and P) and (T and not P) are both consistent]}?

Quantifying over T is probably not going to work. In informal terms that reads like "No logic exists where P is independent", which probably wasn't quite what you wanted, but also we can trivially disprove that with T = {}. As long as P is self-consistent, then "not P" should be too.

We're interested in a proposition's status with respect to some theory that we enjoy (i.e. Zermelo–Fraenkel set theory).

Re: What does “Undecidable” mean, anyway

#138

Post by [deleted] »

Ukv wrote: post #128
bubblyworld wrote: post #124

Earlier quoted context omitted.

That's fair, I've run into a lot of misconceptions like that before. And probably believed some of them at earlier points in my life =P (Roger Penrose himself makes a version of that claim in "the Emperor's New Mind", so we're in good company...) About the bcrypt thing... yeah, so one way you can do it is write a program that generates all possible keys starting with the letter 'a', and tests them. Then you run your…

> About the bcrypt thing... yeah, so one way you can do it is write a program that generates all possible keys starting with the letter 'a', and tests them. Then you run your halting oracle on that, and if it returns true you know the first letter of the key is 'a'. And you really can do that. For actual computers we have cycle detection algorithms that can tell you definitively if your program will halt or not. Dete…

[deleted]

Re: What does “Undecidable” mean, anyway

#139

Post by bubblyworld »

Ukv wrote: post #128
bubblyworld wrote: post #124

Earlier quoted context omitted.

That's fair, I've run into a lot of misconceptions like that before. And probably believed some of them at earlier points in my life =P (Roger Penrose himself makes a version of that claim in "the Emperor's New Mind", so we're in good company...) About the bcrypt thing... yeah, so one way you can do it is write a program that generates all possible keys starting with the letter 'a', and tests them. Then you run your…

> About the bcrypt thing... yeah, so one way you can do it is write a program that generates all possible keys starting with the letter 'a', and tests them. Then you run your halting oracle on that, and if it returns true you know the first letter of the key is 'a'. And you really can do that. For actual computers we have cycle detection algorithms that can tell you definitively if your program will halt or not. Dete…

The conversation is going in circles here =) I agree with everything you have written.

Re: What does “Undecidable” mean, anyway

#140

Post by aeneasmackenzie »

turboponyy wrote: post #120
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.

> It's better to say that some functions like "does this program halt?" simply don't exist. Let f : (p: String) -> Boolean equal the function that returns True if p is a halting program, and False otherwise

This is really just the constructive/classical argument but I want to be specific.

You just named a function and specified a property you want it to have. However no function with this property meaningfully exists. We can manipulate the symbol just fine, but we can never look inside it because it’s not real. Classical mathematics was developed before computation was relevant and the question of decidability arose fairly late, it makes more sense to consider it an early attempt at what is now called intuitionistic mathematics. The halting problem disproved excluded middle.

Post reply on HN