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

91–100 of 196 posts

Re: What does “Undecidable” mean, anyway

#91

Post by skydhash »

nitwit005 wrote: post #77
skydhash wrote: post #57

Earlier quoted context omitted.

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.

Jump is not required for a Turing machine, only being able to move to a specific case by sliding. Conditional jump is an abstraction. Just like looping.

Re: What does “Undecidable” mean, anyway

#92

Post by paulddraper »

hwayne wrote: post #63
wat10000 wrote: post #48

Earlier quoted context omitted.

I'm not sure about that. These are also easily solved with a general-purpose CPU, if you don't care about running time. And there's nothing that says that a halt detector would be fast. The impossibility result is more interesting than just "it would take a million times the age of the universe to complete if every atom in it were put to the sole purpose of computing it" as we often see with cryptography.

That's not necessarily true. Consider the program `x := 4; loop {if !sum_of_two_primes(x) {return true}; x += 2}`. If we run this on a general purpose CPU, this will halt if and only if Goldbach's conjecture has a counterexample. Otherwise it will run forever. So even if a working halt detector takes 14 million billion years, it will definitely tell us if the conjecture is true or not. Whereas if the general purpose…

They’re saying that chess and bcrypt and some others can be brute forced.

You are correct that Goldbach cannot be proven true via brute force. But again, a hypothetical general halting machine may require impractical time — 14 million billion years.

So the idea that “if this existed we crack all sorts of hard problems/optimize” is not necessarily true.

Re: What does “Undecidable” mean, anyway

#93

Post by Dylan16807 »

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…

For that definition, including the phrase "ad infinitum", then it's pretty unlikely.

But a lack of infinities won't prevent the basic scenario of tech improving tech until things are advancing too fast for humans to comprehend.

Re: What does “Undecidable” mean, anyway

#94

Post by Dylan16807 »

andoando wrote: post #62
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.

Turing machine works going left or right writing/reading on a tape of 1s and 0s. Your CPU works on RAM writing and reading 1s and 0s. CPU in principle isn't that different and is largely just using a more sophisticated instruction set. Move 5 vs right right righy right right. swap vs read, write, right, write. etc Definitely not necessary for programming but it's not some completely theoretical mumbo jumbo. Moreover…

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 going to be a byzantine nightmare.

Being restricted to tape, and in particular a single tape, makes Turing machines absolutely awful for teaching programming or how a CPU implements an algorithm. Instructions, data, and status all have to fit in the same place at the same time.

It's so bad that Brainfuck is an order of magnitude better, because it at least has separate instruction and data tapes.

from your other comment > But as far as understanding computer science, computational theory, etc certainly you'd want to study Turing machines and lambda calculus. If you were say, writing a programming language, it would be nice to understand the fundamentals.

Turing machines are not fundamental. They're just one way to achieve computation that is close to minimal. But they're not completely minimal, and I strongly doubt studying them is going to help you make a programming language. At best it'll help you figure out how to turn something that was never meant to compute into a very very bad computer.

Re: What does “Undecidable” mean, anyway

#95

Post by jonahx »

Dylan16807 wrote: post #90
jonahx wrote: post #85

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. > So the blog post's claims that a hypothetical halting algorithm would solve anything "overnight" are exaggerated and naive. I agree "overnight" is misleading in this context. However, I am fairly sure the author is aware of the point you are making.

> "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 case, and why.

Re: What does “Undecidable” mean, anyway

#96

Post by bubblyworld »

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…

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 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)

Also note that "states" in your sense are not the same as "states" in a Turing machine (which are just one of the inputs to the transition function). There are Turing machines with less than ten thousand states whose behaviour is undecidable in ZFC (https://arxiv.org/abs/1605.04343).

Re: What does “Undecidable” mean, anyway

#97

Post by dmurray »

ummonk wrote: post #80
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.

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 computer can do this, then your intuition is wrong.

Program optimizers and theorem provers also exist, of course, but in those cases the problems really are undecidable so no Turing machine is guaranteed to work on any given program or theorem.

Re: What does “Undecidable” mean, anyway

#98

Post by yusina »

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…

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 has this much time to spare has likely already done that elsewhere. But I'd be happy to be wrong and would welcome if just a single person gained better understanding through your text.

What I would suggest though is to avoid using the term "random" for this. I know you put it in quotes, but that term is so over-misused that we do it a disservice by adding more misuse. Numbers (or other objects) are not random, it's the process that produced them in some context that's random. Random processes have very specific, mathematically well-defined properties, just like the concept of decidability has, and throwing around the term with other meanings really does it a disservice, similar to doing the same for decidability.

What you are probably looking for is a term like "arbitrary".

Re: What does “Undecidable” mean, anyway

#99

Post by ummonk »

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 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 whether the proof finding algorithm will ever halt, and thereby find out whether the theorem is provable or not.

Re: What does “Undecidable” mean, anyway

#100

Post by bubblyworld »

dmurray wrote: post #97
ummonk wrote: post #80

Earlier quoted context omitted.

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

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 words, you can use undecidability of first-order logic to prove undecidability of the Halting problem if you like, although it's a bit of a chicken-egg thing historically (I believe).

Post reply on HN