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

141–150 of 196 posts

Re: What does “Undecidable” mean, anyway

#141

Post by bubblyworld »

Xcelerate wrote: post #133
Ukv wrote: post #121

Earlier quoted context omitted.

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

What is the halting sequence? It isn't mentioned in your linked article anywhere (or on google), and makes the rest of your response a little hard to make sense of.

Re: What does “Undecidable” mean, anyway

#142

Post by theodorethomas »

Can someone explain to me why although we've known that classical physics is not a correct description of the hardware of the universe for at least 100 years now, we are still hooked on 90-year-old Turing Machines which cannot physically exist (they violate quantum mechanics) and whose theoretical limitations are, consequently, irrelevant.

Re: What does “Undecidable” mean, anyway

#143

Post by Xcelerate »

bubblyworld wrote: post #141
Xcelerate wrote: post #133

Earlier quoted context omitted.

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

What is the halting sequence? It isn't mentioned in your linked article anywhere (or on google), and makes the rest of your response a little hard to make sense of.

He mentions it on the second page:

> any Martin-Lof random sequence that computes (i.e. allows computing from it) a consistent completion of PA also computes the Halting Problem H; and by deLeeuw et al. [1965], only a recursive sequence (which H is not) can be computed with a positive probability by randomized algorithms.

It's just the sequence of the solutions to the halting problem, i.e., the characteristic function of the halting set. Levin points out this sequence is not recursive/decidable.

Re: What does “Undecidable” mean, anyway

#144

Post by dooglius »

skydhash wrote: post #130
dooglius wrote: post #116

Earlier quoted context omitted.

Suppose I were to teach theoretical CS using only RAM models of computation, with no reference to Turing Machine tapes. Would there be any downside to doing this, pedagogically? (Other than, of course, the backward compatibility concern of students being able to engage with existing literature, which is the main reason this isn't done I think)

You could do this with the C abstract machine. because it’s Turing complete. But we go with TM because they’re the most basic. Anything else is an abstraction. So you can stop at any level you like.

In what way is a TM the most basic? If you mean in terms of simplicity I think a queue automatic is simpler to explain.

Re: What does “Undecidable” mean, anyway

#145

Post by tel »

cubefox wrote: post #111
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…

I still think what I said was correct. > 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”. Yes, but that just means that independence/undecidability…

Yeah, I agree. "Independence" is fundamentally a property of the formal system you're working within (or really, it's a property of the system you're using and of the axiomatic system under test, the system a proposition would be independent from). I'm holding out a bit to unify that with "undecidability" because undecidability takes on a particular character in constructive systems that happens to align with Turing's notion.

So at some level, this was just an acknowledgement that "undecidability" in this form is well represented in formal logic. In that sense, at least in constructive logics, it's not just a synonym for "independence".

Re: What does “Undecidable” mean, anyway

#146

Post by jonahx »

ummonk wrote: post #114
jonahx wrote: post #109

Earlier quoted context omitted.

> for proofs of finite length in general, not just some fixed finite length. For a brute force proof finder, for your program to be guaranteed to finish in theory, you have to pick a length. So it is fixed. Ofc you can choose whatever length you want. But you don't have that constraint with the halting oracle. Perhaps we're saying the same thing?

For the program to be guaranteed to finish in theory, all that is required is that a valid proof exists. You don't have to pick a length in advance - the program just has to keep trying proofs of progressively longer lengths.

But it won't finish if there is no proof! A halting oracle will finish either way.

Re: What does “Undecidable” mean, anyway

#147

Post by Dagonfly »

Ukv wrote: post #125
yusina wrote: post #117

Earlier quoted context omitted.

And how does your decider recognize that a state has been attained twice? If I make the input system large enough then you don't have enough space in your decider to save all the states which it has observed.

> If I make the input system large enough then you don't have enough space in your decider to save all the states We have cycle detection algorithms that don't require saving all states and work in the same big-O space complexity (constant factor overhead) as just running the input system normally without cycle detection. To my understanding that means that, for any input system that runs in finite-but-unbounded spac…

Assume your cycle detection D(TM, i) always outputs 1 when TM(i) doesn't halt (TM is the encoding of a turing machine and i is the input to TM). Otherwise, if TM(i) halts, D does NOT halt. [1]

We can construct a new turing machine F(TM) = D(TM, TM). That is: We ask D to detect a cycle when a TM receives its own encoding as an input. What is the output of F(F)?

F(F) = D(F, F) = 1 can only happen if your cycle detector detected a cycle in F(F) which we just saw terminates with 1. If F(F) doesn't halt, then your cycle detector claims that F(F) terminated, which it doesn't.

Therefore no such cycle detection can exist. It either has to bound the size of the input system or be non-exhaustive in its detection. The intuition here is: Assume the encoding of D has size N and D can check all encodings up to size N, then D must be able to dectect its own cycles. But the input to D(F, F) is size 2N (cause F is roughly the same size as D).

[1] If your original cycle detection outputs 0 if no cycle is present, then just wrap it in a TM that calls the original cycle detection and either returns on 1 or infinite loops on 0.

Re: What does “Undecidable” mean, anyway

#148

Post by [deleted] »

skydhash wrote: post #91
nitwit005 wrote: post #77

Earlier quoted context omitted.

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.

[deleted]

Re: What does “Undecidable” mean, anyway

#149

Post by skydhash »

dooglius wrote: post #144
skydhash wrote: post #130

Earlier quoted context omitted.

You could do this with the C abstract machine. because it’s Turing complete. But we go with TM because they’re the most basic. Anything else is an abstraction. So you can stop at any level you like.

In what way is a TM the most basic? If you mean in terms of simplicity I think a queue automatic is simpler to explain.

The usual theory of computation textbooks usually goes on to explain finite automata first, then context free grammar and finally the Turing machine. Why? Because the execution part of a TM is a finite automata, while the instructions can use the generative process of CFG. And then you got the whole computing world. Just from these principles (the other chapters are mostly about what's possible and what's not and exploration of other properties)

The nice thing about finite automata is that they can be composed together. That leads to a recursive pattern. This leads to the creation of higher abstractions, leading to general purposes CPU and special processors (gpu, npu, cryptographic chipset, hardware encoding,...). The same things applied to CFGs lead to the creation of programming languages.

Re: What does “Undecidable” mean, anyway

#150

Post by nitwit005 »

skydhash wrote: post #91
nitwit005 wrote: post #77

Earlier quoted context omitted.

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.

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