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

151–160 of 196 posts

Re: What does “Undecidable” mean, anyway

#151

Post by Animats »

bubblyworld wrote: post #124
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…

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…

> (Roger Penrose himself makes a version of that claim in "the Emperor's New Mind", so we're in good company...)

Right. That leads to the whole 'brains are special and analog and quantum or something and thus can't be emulated digitally' line of thought. That line of argument is looking rather threadbare since LLMs got good. That's a different issue than decidability, though. Penrose does raise a good question as to how biological brains get so much done with so little power and rather low-frequency signals.

Re: What does “Undecidable” mean, anyway

#152

Post by Animats »

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…

Right. Cycle detection can be done by running two copies of the program in lockstep, but at a 2:1 step rate. If the state of both programs match, you're in an infinite loop.

Re: What does “Undecidable” mean, anyway

#153

Post by Ukv »

Dagonfly wrote: post #147
Ukv wrote: post #125

Earlier quoted context omitted.

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

I believe the problem there is that the constructed F(F) input itself would not run in finite space:

* F(F) internally runs its implementation of D's code on (F, F)

* ...which runs F(F) plus some constant-factor-overhead

* ...which runs its implementation of D's code on (F, F)

* ...which runs F(F) plus some constant-factor-overhead

* etc.

Ends up with the F emulating itself recursively, with the overhead adding up.

Note that the claim I make of D is that for any input system that runs in finite-but-unbounded space it will determine whether it halts in finite-but-unbounded space - not for input systems that already by themselves use infinite space.

Re: What does “Undecidable” mean, anyway

#154

Post by skydhash »

nitwit005 wrote: post #150
skydhash wrote: post #91

Earlier quoted context omitted.

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.

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 like lambda calculus and Hoare logic. They all can be mapped to each other. So what we usually do is to invent a set of abstractions (an abstract machine) that can be mapped down to a TM-equivalent. Then denote those abstractions as primitives and then build a CFG that we can use to instruct the machine.

In the case of CPUs, the abstractions are the control unit, the registers, the combinational logic, the memory,... and the CFG is the instruction set architecture. On top of that we can find the abstract machine for the C programming language. On top of the latter you can find the abstract machine for programming language like Common Lisp (SBCL) and Python.

It's turtles all the way down. You just choose where you want to stop. Either at the Python level, the C level, the assembly level, the ISA level, or the theorical TM level.

Re: What does “Undecidable” mean, anyway

#155

Post by andoando »

dooglius wrote: post #116
andoando wrote: post #70

Earlier quoted context omitted.

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

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)

If you were teaching theoretical CS, I think you'd certainly want to use a lower level abstraction than RAM. (And RAM really is not unlike a Turing machine tape, except its chunked in bytes and addressable, but in principle plays the same role and has the same operations that can be performed on it which is, move to the left, move to the right, read at the current location, write to the current location. And the modern CPU instruction set isn't really all that different in principle either as if you look at it, its mostly using higher level instructions for accomplishing the aforementioned operations. Eg. Move x, versus 5 right or left operations. But you can certainly write a Turing Machines which implement such an instruction set, and have an easier programmable Turing Machine).

Now TMs certainly are not the only more fundamentals models of computing, but they are certainly interesting nonetheless, and have an for the influence for the Von Neuman Architecture and modern computers.

If I were studying theoretical CS, Id want to learn about TMs, lamba calculus, FSMs, queue automatica, all of it. If you just told me about how modern computers work, Id be left wondering how anyone even conceived this idea.

And as I said in my earlier comment, when you get down to the core of it, what's really interesting to me, and this is readily apparent if you reading Turing's 1936 paper, is that Turing very much came up with the idea thinking about how HE does computation on graph paper. That to me is such an essential fact I would not have want to missed, and I wouldn't have known it lest I actually read the paper myself.

Re: What does “Undecidable” mean, anyway

#156

Post by bubblyworld »

Xcelerate wrote: post #143
bubblyworld wrote: post #141

Earlier quoted context omitted.

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

Thanks - I have to admit there's far too much jargon in there for me to make heads or tails of the main claims, let alone say anything sensible about your original reply. I can't even work out how your statement that no algorithmic process can increase the mutual information between two given strings is formalised in the language of the paper, since there seems to be an obvious counterexample - the mutual information between an infinite string of 0s and the halting sequence can be made arbitrarily large by a program with oracle access to the halting sequence by simply transforming each element into the corresponding element of the halting sequence. So of course I am missing something.

But it seems interesting, thanks for the link =)

Re: What does “Undecidable” mean, anyway

#157

Post by Maxatar »

jonahx wrote: post #146
ummonk wrote: post #114

Earlier quoted context omitted.

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.

Sure, but neither bcrypt or chess fall into the category of being unprovable, so having a halting detector doesn't help for those situations. The author is mixing up problems that are "hard" in the sense that we know in principle how to solve it but need a lot of resources, versus "hard" in the sense that we genuinely don't know how to solve the problem, even if we had access to infinite resources.

Mixing these two up is very misleading and detracts from what is otherwise a well written article.

Re: What does “Undecidable” mean, anyway

#158

Post by Maxatar »

bubblyworld wrote: post #100
dmurray wrote: post #97

Earlier quoted context omitted.

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 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. Now please use it to prove or disprove the continuum hypothesis (within ZFC).

Hopefully you'll come back to me and say the black box shows that the continuum hypothesis can not be proved or disproved (in ZFC). Okay we agree so far, but note that we have established that having a solution to the halting problem can not actually be repurposed as a general purpose theorem prover, since no such proof exists in the first place.

Okay you might counter by saying that a solution to the halting problem can be repurposed as a general purpose theorem prover for propositions that either have a proof or don't have a proof, ignore those pesky propositions that are neither provable or unprovable...

But then the solution to the halting problem doesn't get you anything... if you're dealing with a proposition that either has a proof or a proof of its negation, you don't need a solution to the halting problem to find it, you are guaranteed to find it eventually by definition.

The claim that a black box that solves the halting problem can be used as a general purpose theorem prover is simply untrue and confuses certain concepts together. At best you can claim it gives you a restricted theorem classifier.

Re: What does “Undecidable” mean, anyway

#159

Post by joe_the_user »

bawolff wrote: post #50
joe_the_user wrote: post #33

Earlier quoted context omitted.

I don't either philosophical conceptions of consciousness or theories of computational complexity count as even "efforts to formalize intelligence". They are each focused on something significantly different. The closest effort I know of as far characterizing intelligence as such is Steven Smale's 18th problem. https://en.wikipedia.org/wiki/Smale%27s_problems

The wikipedia article is pretty useless here. The original paper is better, but still seems to be too vauge to be useful. Where it isn't vauge it seems to point pretty strongly to computability/complexity theory. Intelligence means many different things to different people. If we just gesture vaugely at it we aren't going to get anywhere, everyone will just talk past each other.

Yeah,

Smale is a very smart person but his stuff indeed seems as much a vague gesture as the other efforts. I feel like neural networks have succeeded primarily because of the failure of theorists/developers/etc to create any coherent theory of intelligence aside from formal logic (or Perl, formal probability). Nothing captures the ability of thinking to use very rough approximations. Nothing explains/accounts-of Moravec's Paradox etc.

Re: What does “Undecidable” mean, anyway

#160

Post by Dylan16807 »

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…

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 value, but niche value at that point. I wouldn't call it important if you already understand the very low level, and you should not use it as the model for teaching the very low level.

Post reply on HN