Hacker News Reader

Comment by cheradenine01 | Hacker News Reader

Nope. Go read Penrose.

There are problems that the brain can solve, but you can (provably) show that an algorithm cannot. For example - tesselation on an infinite plane.

View on HN

Nope. Can I suggest you read Penrose again with a little more critical thought.

There are problems it is possible to prove are not computable. But can you prove that human beings can solve them?

Tessellation of the infinite plane? Please demonstrate a person that can solve this (i.e. not that they have a > 99.9% chance of being able to do it, or that you can show they can start out pretty successfully and you assume they'll always stay ahead of the game).

Bear in mind when working out if a computer can solve a given problem (i.e. is it mathematically computable), we're not trying to work out if it can ever solve it, or even if it can solve it in infinitely many cases, or even in an arbitrarily high proportion of cases. We're working out if it can be proven that it is (not) guaranteed to find a correct solution in all cases. There's just no way to make those judgements of a human being.

So instead, mathematical analysis of computation is compared against intuition arguments from the evidence that human beings have good, reliable strategies for solving some of them. Unsurprisingly, the brain comes off pretty well in that comparison!

Penrose was big on handwaving and appeal to quantum magic, but not very good on the specific arguments to back up his claim.

I found this article to be a huge bag of misconceptions about AI, computation, and the actual claims of AI professionals. As an argument against hyperbolic media mischaracterisation, it might be reasonable. But like Penrose, it manages a long and condescending argument from intuition that fails to take seriously the actual claims being made.

[Edit: for clarity and spelling]

> But can you prove that human beings can solve them? > Tessellation of the infinite plane? Please demonstrate a person that can solve this

Penrose himself would seem to be a demonstration that there is at least one person, IIRC.

Is your argument that uncomputable really just means no guaranteed success, and that just because some human can get a solution to an uncomputable problem doesn't mean that it isn't following a set of algorithms?

You misunderstand the result Penrose has shown. There are plenty of aperiodic tessellations of the plane that can be computationally generated. The issue is whether a computer can, in all cases, determine if a set of shapes can tile aperiodically.

I don't understand the second bit. But, no. Computability has very specific definition. Getting a solution to an uncomputable problem isn't generally hard. It is trivial to create a program that will solve the halting problem for an infinite class of cases. The issue is that such solutions can be shown not to be general over all cases.

Such overconfidence. There is no generally accepted evidence that anything physical, whether brain or something else, can compute something a TM cannot compute. Penrose's claims are conjectures at best and pseudoscience at worst.

Since the brain is not just a Turing machine, it would be astonishing if it was limited to the capabilities of a Turning machine. The brain is capable of emulating a Turning machine, but that is just one of its capabilities.

The things a Turing machine lacks are interupts and I/O. If you hook sensors up to a Turing machine and make the tape change depending on the state of those sensors, you don't have a Turing machine any more, in the sense that it is no longer bound by any of Turing's computability theorems.

This insistence that the limits of the most limited model of computing (Turing machines) must be applicable to any machine that computes anything--including things that are not describe by any of the formal mathematical proofs on the limits of computability because they violate the most basic assumptions upon which those proofs depend--is one of the most curious aspects this debate.

So not even computers are just Turing machines, because they too have I/O. Turing's theorems are useful and important when considering certain practical questions of computability within the limited circumstances of a computation whose inputs are entirely specified at the start and which can't be interrupted by new information coming from the outside, but they just don't apply to cases where there are cells whose values aren't known until reality provides them via some sensor mechanism.

As such, it would be a little weird if we (and computers) can't compute things a Turing machine can't, given we have capabilities that a Turing machine doesn't have. There are even examples of such things. One due to Church (IIRC) that shows how we can solve certain instances of the halting problem that a Turing machine can't.

Actually Turing's paper "On Computable Numbers" distinguishes between "automatic machines" (a-machines) and "choice machines" (c-machines), where the latter can pause to ask for input. It seems to me this accounts for your I/O. (I think this is also how you'd add a RNG to a Turing machine.) His paper pretty much only considers a-machines, so I'm curious what is written about c-machines elsewhere. It's unclear to me how much c-machines "change the story." For instance you can't escape Godel's Incompleteness Theorem by adding a finite number of axioms to fill in all the unprovable statements, because there are infinitely many of them.

Unless interrupts and the Input portion of I/O are generated by an oracle (A machine of a computational class more powerful than UTMs) of some sort, a Turing Machine with I/O and interrupts is equivalent to a UTM. I remember the proof being trivial, ie some guys did it during my CS undergrad for a short (2-week) research introduction course, but I can't find a proper paper about it atm. Granted, if the brain was an oracle, this would be true, but you would have to presume that the brain was an oracle in order to prove that it is stronger than a UTM.

In regards to your last statement, the other way works as well. There are statements that can't be proved by any human brain, but can be proved by non-brain logical systems. For example: "The brain cannot consistently assert this statement". One can then create instances of types of problems that are equivalent (when put through some bijective transformation) to the beforementioned statement.

The Emperor's New Mind (and the followup whose name I forget).

There's a rather scratchy recorded documentary here https://www.youtube.com/watch?v=eVq39QbFQXE

See also: https://en.wikipedia.org/wiki/Wang_tile n 1966, Wang's student Robert Berger solved the domino problem in the negative. He proved that no algorithm for the problem can exist, by showing how to translate any Turing machine into a set of Wang tiles that tiles the plane if and only if the Turing machine does not halt. The undecidability of the halting problem (the problem of testing whether a Turing machine eventually halts) then implies the undecidability of Wang's tiling problem.

I googled for tessellation infinite plane algorithm but could not find any pertinent information.

There are problems that the brain can solve that one can prove an algorithm cannot. That to me is a bold claim. Could you point to material I could read on this?

It's a confusion of the algorithm that the brain implements with the algorithm that implements the brain.

Penrose fills in the gaps with quantum woo. He's much beloved by people who can't quite bring themselves to quote Deepak Chopra.

Thank you for the straight-shot no-nonsense clarification. :)

I would not discount Penrose with the ease the GP does. These themes are quite philosophical, therefore all sides are making some big assumptions. I would read Penrose, Dennett, Chalmers, Tononi, Searle, Putnam and many others. In philosophy the trick is to disagree with everyone.

Agreed. I am very intrigued by Penrose but not convinced. In Scott Aaronson's online lectures for Quantum Computing since Democritus he is pretty dismissive of Penrose, but in the book he asks why a renowned Oxford scholar would insist on such a position, and that's a good question! In these arguments people are too willing to clamp shut their opinion and shut down wonder.

Reply on news.ycombinator.com