I think the interesting question here is whether Penrose is claiming that the things of which the brain is capable (most notably the production of consciousness) are inherently non-computable by _any_ kind of artificial device, which is effectively a form of vitalism, or whether he is claiming that they _might_ be computable, but only with a quantum computer.

Quantum computers are computable by classical computers. It's just a problem of exponential complexity.

Penrose argues just in terms of classical computers

> shouldn't it, by definition, be computable

By which definition? Why does anything that is "physically grounded" and "achievable" be computable?

Meanwhile, I don't know what "physically grounded" and "achievable" mean in this context.

No. Why should it be?

If it's physically grounded then it would be computable by some machine, just not necessarily a Turing machine. For instance, a hypercomputer can solve the Halting problem for Turing machines. We just have to be clear about the kind of machine on which a problem is computable.

> If it's physically grounded then it would be computable by some machine, just not necessarily a Turing machine.

What makes you think that? The overwhelming majority of functions aren’t computable. The evidence suggests, if anything, that the universe is uncomputable and at best some isolatable well-measured specific phenomena can have approximations computed to some arbitrary but inexact precision.

> What makes you think that?

Because if it's physically grounded then you can build a physical analogue of it.

> overwhelming majority of functions aren’t computable

By Turing machines, not by any other type of machine. As I said, if hypercomputers exist then they can solve the Halting problem, which Turing machines cannot.

Consider the set of functions that that map the reals onto other reals. Almost all of these functions are truly random, with no way of expressing them that does not require the storage of an infinite number of infinite strings.

Not only is there no practical way of creating such a thing, most formulations of physics preclude any possibility of making one by placing finite limits of the amount of space or time accessible to us.

(Not to mention that almost all reals are [Turing] uncomputable in their own right, but that's a more complex thing to demonstrate.)

You don't need to express or encode the reals if you've built a physical analogue that operates on those reals, that's the point.

It depends on if the universe is fundamentally deterministic or not. Right now we don't have any way to see beyond the apparent randomness in quantum mechanics and we probably never will. This part of the universe might be completely non-computable to us, it's just random.

Randomness doesn't have any real impact on whether a problem is computable. Just model the distribution of the random variable. Non-deterministic Turing machines are a thing.

That's true. I suppose it comes down to what exactly is meant by "is computable". I don't think it was defined well enough, which I suppose is to be expected when discussing these topics that involve lots of hand-waving.

I interpreted it to mean that we can predict the outcome of it, you interpret it to mean that we can model it.

Either way, maybe it doesn't matter since the original proposal is that consciousness is a subjective experience and there isn't an obvious way to define how to programmatically create it i.e. compute it.

You probably mean probabilistic Turing machines. Non-deterministic automata in general don't involve randomness, and the results of their computation are considered to be deterministic despite the name.

And of course all TMs are just theoretical models. Non-deterministic Turing machine equivalents in particular don't physically exist and may be physically impossible.

But of course if there is indeed true randomness in nature that needs to be modelled, that same randomness can be used a source of true randomness for computation, and you can then build computation that does have stochastically determined results.

In your statement, I'm not sure by which definition physically grounded things are a sufficient condition for being computable, but I think Penrose depends on the Turing notion of computability and the hardness of the halting problem.

We can of course move goal posts, redefine computability however we like, to get whatever conclusion we care for, but I think that Penrose effort is intellectually honest.

Computing brain behavior is not the halting problem though. It's a computation of one algorithm.

Yes, just like the algorithm that decides whether any given algorithm terminates could be "one algorithm" (if it was possible) :-)

For that to be uncomputable brain must run the halting problem algorithm, which it doesn't, because the halting problem algorithm needs infinite memory. Being finite, brain has finite number of states, which all can be enumerated in finite time.