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

161–170 of 196 posts

Re: What does “Undecidable” mean, anyway

#161

Post by Dylan16807 »

skydhash wrote: post #154
nitwit005 wrote: post #150

Earlier quoted context omitted.

I suspect you have forgotten this was a conversation about relevance in the day to day.

TM is the basic theory. It's a more advanced finite automata that is able to modify it's own instructions. The latter can be generated from a context free grammar. Both CFG and FA have a recursive nature that allows to build more advanced mechanism from those simple elements. And that's how you get CPUs (and more specialised ones like GPUs, NPUs, etc) and programming languages. There are other computation mechanism l…

A Turing machine isn't the only way to improve a finite automaton to make it universal. It doesn't have to be the bottom turtle.

Re: What does “Undecidable” mean, anyway

#162

Post by nitwit005 »

skydhash wrote: post #154
nitwit005 wrote: post #150

Earlier quoted context omitted.

I suspect you have forgotten this was a conversation about relevance in the day to day.

TM is the basic theory. It's a more advanced finite automata that is able to modify it's own instructions. The latter can be generated from a context free grammar. Both CFG and FA have a recursive nature that allows to build more advanced mechanism from those simple elements. And that's how you get CPUs (and more specialised ones like GPUs, NPUs, etc) and programming languages. There are other computation mechanism l…

I think it's pretty clear you just want to talk about the theory. You're simply ignoring what I'm saying.

Re: What does “Undecidable” mean, anyway

#163

Post by andoando »

Dylan16807 wrote: post #160
andoando wrote: post #113

Earlier quoted context omitted.

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…

And a barebones traditional CPU is a finite state machine plus random access memory. It teaches you mostly the same things about how you put together simple components into universal computation, while having programs that are far easier to comprehend. And then for another perspective on computation, lambda calculus is very different and can broaden your thoughts. Then you could look at Turing machines and get some v…

>while having programs that are far easier to comprehend.

If you want to learn the fundamentals of something, should you not wish to you know, think about the fundamentals?

Re: What does “Undecidable” mean, anyway

#164

Post by Dylan16807 »

andoando wrote: post #163
Dylan16807 wrote: post #160

Earlier quoted context omitted.

And a barebones traditional CPU is a finite state machine plus random access memory. It teaches you mostly the same things about how you put together simple components into universal computation, while having programs that are far easier to comprehend. And then for another perspective on computation, lambda calculus is very different and can broaden your thoughts. Then you could look at Turing machines and get some v…

>while having programs that are far easier to comprehend. If you want to learn the fundamentals of something, should you not wish to you know, think about the fundamentals?

My argument is that FSM+tape and FSM+RAM are at the same level of "fundamental", but one is easier to understand so it should be the thing you teach with. Being more obtuse is not better.

Re: What does “Undecidable” mean, anyway

#165

Post by yusina »

LPisGood wrote: post #134
yusina wrote: post #102

Earlier quoted context omitted.

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.

Exactly, that was my point. Thanks for putting it more succinctly.

Re: What does “Undecidable” mean, anyway

#166

Post by rstuart4133 »

mreid wrote: post #65

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…

> This is a really nice explanation of decidability.

I'm not an enthused about it as you. It doesn't mention that every undecidabilty involves an infinity. What makes a problem undecidable is not that you can't write an algorithm for it, it's that you can't guarantee the spits out an answer in a finite number of steps.

Take the halting problem. He defines it as "does [the Turning] machine M halt on input i?". The answer is famously no. But you can write an algorithm for it, and if you restrict the Turning machine it's analyzing to having a finite tape it will always spit out the correct answer. The problem is the algorithm creates a power set of the Turning machine states. If you run it on a machine with infinite states it potentially needs to construct power set of an infinity. That's not just an infinity, its a new, distinguishable from, and in some sense higher order infinity than the one you started with.

I can't call an explanation nice when it omits the central idea that explains what is going on under the hood. His description of the universality Turning machines on the other hand was nice.

Re: What does “Undecidable” mean, anyway

#167

Post by Tainnor »

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…

Decidability is a term from theoretical CS where languages can be arbitrarily big. It doesn't make sense to repurpose the term for actual finite-memory machines.

Re: What does “Undecidable” mean, anyway

#168

Post by Tainnor »

Maxatar wrote: post #158
bubblyworld wrote: post #100

Earlier quoted context omitted.

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

>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). The author is not correct and it's a common misconception. Simple question for you... let's say I give you a magical black box that can solve the halting problem…

You're mixing things up. By a "general theorem prover", we typically mean "a program which can decide for every sentence in FOL whether it's valid" (I say FOL, because the situation is even worse for HOL), i.e. a decider for the set of valid FOL sentences. The sentence ZFC -> CH (where ZFC and CH are expanded as needed) is not valid because CH doesn't follow from the ZFC axioms. Neither is ZFC -> not(CH) valid. We know both of these results from proofs specific to this problem, but a general purpose theorem prover would give us both of these results for free. If we had such a tool, mathematics would essentially be "solved" (maybe apart from deciding what questions to ask). But since FOL is undecidable, it can't exist.

What you are asking for is a machine that for each pair of formulas A, B (correctly) decides that either A -> B or A -> not(B), but this is impossible for model-theoretic reasons (not all theories are complete) and that has nothing to do with decidability.

Re: What does “Undecidable” mean, anyway

#169

Post by Tainnor »

godelski wrote: post #81

I think it helps to understand my namesake's Incompleteness Theorem[0]. They are actually connected [1,2] 1) no consistent system of axioms whose theorems can be listed by an effective procedure (i.e. an algorithm) is capable of proving all truths about the arithmetic of natural numbers. For any such consistent formal system, there will always be statements about natural numbers that are true, but that are unprovable…

> Any axiomatic system will have true statements that are unprovable.

Any effectively computable axiomatic system of sufficient strength.

The "effectively computable" condition is probably uninteresting (if we couldn't effectively decide if something is an axiom we wouldn't be able to check proofs), but the "sufficient strength" part matters. There are interesting theories that are complete (i.e. for every sentence P, either P or not(P) is a consequence), such as the theory of the natural numbers with addition (but without multiplication).

Re: What does “Undecidable” mean, anyway

#170

Post by Tainnor »

My pet peeves when it comes to undecidability:

1. People saying "sure, problem A may be undecidable but it's decidable for instance X". That's not how the concept works - if you restrict the a problem to a specific instance (in the sense of having a decider for the intersection of A and {X}), then it will always be decidable because either the Turing Machine that always outputs true or the Turing Machine that always outputs false is a decider (it doesn't matter that we don't know which one). I know what people are trying to say - "just because a problem is undecidable it doesn't mean you can't solve specific instances" - but this is arguing against a misconception of what decidability means.

2. "Decidability doesn't matter because real-world computers have finite memory". Yeah, but if your solution to problem X involves running an algorithm until you've run through all possible 2^N configurations for N=the size of your memory, you haven't really practically solved it either in any way that anyone would want to use.

Post reply on HN