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

61–70 of 196 posts

Re: What does “Undecidable” mean, anyway

#61

Post by drdrey »

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 depends what you're working on, if you do any form of program analysis (security, compiler stuff) you bump into undecidability everyday

Re: What does “Undecidable” mean, anyway

#62

Post by andoando »

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.

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 what's really interesting to me is that Turing came up with the idea from following what he himself was doing as he did computation on graph paper

Re: What does “Undecidable” mean, anyway

#63

Post by hwayne »

wat10000 wrote: post #48
cobbzilla wrote: post #8

Earlier quoted context omitted.

I really enjoyed the author’s explanation of undecidability. I found this bit was really helpful: “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'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 CPU is still running after that time, we still have no way of knowing whether it's because it's going to run forever or if it simply hasn't reached the first (ludicrously large) counterexample.

Re: What does “Undecidable” mean, anyway

#64

Post by DonaldPShimoda »

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…

> One of the biggest boost to my SWE career was studying theory of computation and programming languages theory.

I totally agree with you.

> My major was electronic engineering, so I didn't touch those at the university.

Unfortunately, ever more computer science graduates lack the same belief, even if they go to "top" university programs.

Of course, I think part of the problem is the way the material is presented; "learn this to pass the exam" without fundamental motivation is pretty much always a bad set-up to get students interested. But, speaking anecdotally, a large part also seems to be a semi-recent surge of undergraduate students who genuinely believe that their academic career is nothing more than a hurdle to be muddled through in service of getting a piece of paper that lets them get a high-paying, low-labor-intensity job. They just don't engage with theory-focused material beyond what's strictly necessary to graduate, and then they dump the thoughts from their minds the second the semester is over.

This manifests in all sorts of ways, but a common one is undergrads telling one another how little their professors know about the "real world" because they use (not even that) outdated technology in their lectures. Or maybe the profs use some less popular language and the students think of it as a waste of time. There's comparatively little self-motivation among modern CS students, where historically I think there was rather a lot.

I suppose I'm not really going anywhere specific with this other than complaining, so maybe I can ask: What do you think it was that helped you realize that learning fundamental theory would be beneficial? (I don't have any indication that you were the same kind of student as these that I mention, since you were in a different major altogether, but I'm always looking for insights to help motivate students to study theory more, and insights can come from anywhere.)

Re: What does “Undecidable” mean, anyway

#65

Post by mreid »

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 plus its inputs) and outputs True or False depending on whether it halts or not.

The argument in the article does a great job of showing that `IS_HALTING` cannot exist because it is in some sense "too powerful" but that means there is a mapping f : strings -> boolean that cannot be represented as a program, which seems weird if you've been programming for ages and every function you encounter is expressed as a program.

The result becomes less weird when you realize that that almost all functions from string -> boolean are not expressible as a program. Why? Well there are countable many programs since there are only countably many finite length strings and every program, by definition, is a finite length string. However, there are uncountably many functions from string -> boolean since these functions map one-to-one to sets of strings (just let the set be all inputs that map to True) and the cardinality of the set of sets of strings is uncountable.

This is essentially due to Cantor's diagonalization argument which shows you cannot put all elements in a set X into a 1-1 correspondence with all the subsets of X, even when X is countably infinite. This fact is at the heart of a lot of these computability results since it shows there is a gap between all functions (= any arbitrary subset of finite strings) and a program (= a finite string).

Re: What does “Undecidable” mean, anyway

#66

Post by mreid »

nialv7 wrote: post #59

One of my favorite insights is that the existence of undecidable problems is the same thing as the uncountability of real numbers. Too bad the author didn't get into it.

I had exactly the same reaction, which prompted me to write this comment: https://news.ycombinator.com/item?id=44122045

Re: What does “Undecidable” mean, anyway

#67

Post by DonaldPShimoda »

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…

> Definitely not necessary for programming but it's not some completely theoretical mumbo jumbo.

While I'm a big fan of teaching theory, I regret to inform you that the Turing machine is kind of completely theoretical mumbo jumbo. The theoretical equivalent of the modern processor is the Von Neumann machine. Certainly there is a direct connection to be made to the Turing machine, as all computation can be framed as a program run on such a theoretical device, but there is not really much practical use in teaching students that modern computers are Turing machines. There's just too much difference, I think.

The utility of the Turing machine as a pedagogical device stems more from, like, being able to formalize a decidable problem in a particular way, following a rigorous algorithmic approach to computation, thinking about abstraction, etc. I think the lambda calculus is also useful to teach for similar (though also different) pedagogical reasons, but I would never tell students that the lambda calculus "in principle isn't that different" from how their favorite language works. Practically all programming languages can be framed as lambda calculi, but some of them are sufficiently far removed from the theory for that comparison to be mostly useless to the majority of students.

Re: What does “Undecidable” mean, anyway

#69

Post by wat10000 »

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…

I think you're agreeing with me. The problems listed as something that a halt detector can be "trivially repurposed" for are problems that a normal CPU can also be trivially repurposed for (ignoring the issue of execution time), and my understanding is that normal CPUs are not impossible. The halting problem is different because it is provably impossible even with unlimited resources unless you're somehow able to make something more capable than a Turing machine.

Re: What does “Undecidable” mean, anyway

#70

Post by andoando »

DonaldPShimoda wrote: post #67
andoando wrote: post #62

Earlier quoted context omitted.

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…

> Definitely not necessary for programming but it's not some completely theoretical mumbo jumbo. While I'm a big fan of teaching theory, I regret to inform you that the Turing machine is kind of completely theoretical mumbo jumbo. The theoretical equivalent of the modern processor is the Von Neumann machine. Certainly there is a direct connection to be made to the Turing machine, as all computation can be framed as a…

I'm not sure what were arguing to be honest. You definitely don't need to understand Turing machines to understand how computers work, and certainly not how to do programming.

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.

I mean, I don't think Turing machines or Lambda calculus are even that far removed to call them completely theoretical. You can easily implement a few functions in lambda calculus that already resemble modern programming interfaces.

Post reply on HN