Agreed. A Turing machine operates in a discrete countable state space, whereas the human brain requires real numbers for a complete state description. Cantor showed (with the diagonal argument) that real numbers are uncountable - so there are (infinitely many!) real numbers that are unreachable using a Turing machine. My suspicion is that AGI, consciousness, perhaps even the supernatural soul you allude to, can be found only in this unreachable state space. There exists a Cardinality Barrier!
Good article. The issue is that his parallel computation isn't itself a Turing machine.
If you build a system which can "keep pace with the diagonalization argument", necessarily, it isnt a computer.
No computer can process at the rate real numbers require, this is another way of stating the Cantor result.
If you build a computer (here, note, computer = an abstract mathematical formalism over discrete numbers), you cannot compute fast enough.
I happen to think reality, esp. spacetime, is geometric (ie., real-valued) though empirical measures of it are, of course, just a discrete approximation.
A key part of Turing's computability paper hinges on the diagonal argument. It's really well covered in 'The Annotated Turing' by Charles Petzold.
In Cantor's version, we prove that numbers (real numbers?) are not enumerable by creating a new number.
In Turing's paper, he enumerates all valid Turing machines in a similar way, but crucially, we can't know if the new constructed machine is valid or not, so the outcome is different.
It's quite possible I'm botching elements of these, but it was a beautiful read.
Given that Cantor’s Diagonal Argument – which demonstrates the existence of uncountable sets – is the technique which underlies Turing’s solution to the Entscheidungsproblem, you might want to re-examine your assumptions.
> Undefinable real numbers exist, whether you can compute them or not.
I agree with you, but as you probably know this is a deep ontological question. The meaning of something "existing" has been debated for many centuries, especially for cases such as this.
> A theory of computation that rejects the existence of things that can't be computed is like a logic that rejects the existence of FALSE because it can't be proved. Where does the busy beaver function sit in your conceptual model?
There is a difference between rejecting and classifying. I am not proposing a new computational model. Turing's model classifies the busy beaver function as non-computable. Correct?
I thought we were discussing Church-Turing. This assumes Turing Machines, and what they can compute. Of course you can break everything by assuming an imaginary machine that can compute functions that are not computable by Turing Machines...
Our machines _can_ compute any Turing-computable function, except only up to some finite point because we must exist in this reality. Our numbers are infinite, but we do not argue they are not because someone was not able to count up to 999999999999999999999999999!
> "I am not assuming anything other that what you wrote"
Yes you are:
> "it works just as well to consider humans to be char programs which map strings to strings."
Before proceeding, I will assume you're familiar with the distinction between countable and uncountable infinities, and the Cantor Diagonalization proof [0]. This argument is simply a special case of that.
Mapping strings to strings is an uncountable infinity (it's the powerset of countable infinities). All possible machine programs are a countable infinity (since any given source program is finite). The argument "give me an output other than what any of these programs would give" mimics the diagonalization step -- it demonstrates that, whatever is in the infinite list of possible AI programs, you can construct string mappings that none of the AI programs would have constructed.
Yet a strong AI should be able to construct any string mapping whatsoever. Thus, "strong AI" and "running finite source code" are necessarily incompatible. (We do not know whether human programming is enumerable; thus, we cannot draw the analogy you attempted to draw.)
Seems rather conveniently coincidental that the computable reals might be the only reals found in nature.
I'd also suggest that there are plenty of equation systems that in fact cannot be solved, by Turing machine or otherwise. The 3 body problem comes to mind.
Perhaps a Turing machine could emulate the human brain, however maybe you'd need all the atoms in the known universe to get to the required fidelity.
Of course, the idea that a computer can do anything is rather attractive to those who are experts in computers. It is wrong though.
No, a Turing complete system can perfectly simulate any other discreet (digital) computation system.
What it cannot do is perfectly simulate any analogue system. By Cantor's diagonal argument, there are vastly more real numbers than natural numbers. Any system that is completely definable in the natural numbers (like digital computers) will not be able to 'reach' the vast majority of real numbers (in case you are concerned about the existence of real numbers, what is the square root of 2? What is the ratio of diameter to circumference?). Throw in some Chaos Theory and you can see how far away any Turing complete system is from a biological brain.
Sure- if you have access to exact real numbers, you have something more powerful than a Turing machine. But there's no evidence that that's physically possible. The Church-Turing thesis is about actual computation that could happen in the world, not theoretical models, of which there are many that can perform hypercomputation.
It's been a long time since I had my Theory of Computation class, but as I recall, the proof that there are computationally undecidable questions uses the same diagonalization technique[1] used to demonstrate that the real numbers are not countably infinite.
The same technique can be used to show there are still computationally undecidable questions if you have a Turing Machine with an Oracle.
This proof technique suggests not only are there undecidable questions, there are uncountably many of them. Even if you have an Oracle.
Well, those functions are called uncomputable because, as far as we know, there is no repeatable way of computing them, right?
So if the human brain was able to compute functions that Turing machines can't, it doesn't mean those functions are uncomputable, it just means the Church-Turing hypothesis is false.
Or on any computer at all, even an “infinite” (at least unbounded) computer like a Turing machine, considering that almost all real numbers are not computable.
I have thought of this as framing a paradox for the impossibility of strong AI. Turing machines can never really be embodied. They can always move to a different substrate. So intuitively, they don't have skin in the game in the same way that living things do. Mathematically, they are unable to represent the real numbers, only the rational numbers.
Maybe this intuition is what you're getting at here.
That said, our Turing Machine model of computation is discrete, and the Church-Turing thesis implies human thought is Turing Complete.
It's not empirical evidence, but it's something. (I really doubt an empirical test is possible at all, so it seems philosophizing is all we have, unfortunately.) I'm not aware of any (communicable) model of thought that actually can't be reduced to the Turing model (in fact, that AFAIK precisely the reason he proposed the model).
Analog signals can be approximated to arbitrary precision, so while we conventionally think of it as continuous, it doesn't imply our cognition really has infinite precision floats internally...
I think it's really unfair to only focus on half of the picture (saying there's no evidence for "Cognition is discrete") where in fact we actually have no evidence at all whether anything is fundamentally continuous or merely approximated as such with high precision.
Traditionally the math in physics is continuous, and the math in computing is mostly discrete. If people point to Hilbert space as some kind of justification for believing physics is continuous, then it seems equally valid (or invalid) to use the Turing model as justification to believe cognition is discrete. I think both approaches are misguided, but as I said, it's really unfair to point out only the convenient half of these invalid arguments.
Also, the limits of computation have been given an upper bound. If it's not computable by a Turing machine with a finite memory tape (or anything else that is mappable to a Turing machine with a finite memory tape), it's not computable by a physical computer.
Steve Yegge started exploring the metaphysics of computer programs before he stopped blogging; it makes for interesting reading.
"And indeed CPUs as turing complete, programmable machine are a strict superset of what brains can do."
This is a fundamental assertion that I do not believe you can make.
The brain cannot simulate a turing machine. It does not have infinite memory, which is a requirement for a turing machine. It can, however, stimulate a linearly bounded automata.
It is also not implicitly obvious that a turing machine can simulate a brain. The primary difficulty that I do not yet see a way around is the fact that a turing machine, which has as its control unit a finite State machine, is bound by the finiteness of those states (finiteness of representation, not of number). The brain has no such constraint. It is analog, and therefore infinite in State representation.
In my opinion, this is more akin to the P versus NP problem, and that we know what needs to be equivalent in order to say that P equals NP, but no one has proved it or disproved it yet. That's how I feel about the statement about Turing machines and the brain. I do not believe we can be dogmatic on that aspect yet either way. We may have opinions, just as we may have opinions about P vs NP, but we must also be careful about stating what is provable and what is opinion, and that is all I'm trying to do.
Of course, I am willing and very interested to gain more insight in this area, so discussion is welcome!
Suppose we have some intelligence that cannot be simulated in a Turing machine because it invokes an uncomputable function. That intelligence as it exists in reality is computing something that cannot be computed by a Turing machine. It's not impossible that that can exist (quantum computers may someday demonstrate that, for example), but it would be a huge discovery that would shake the foundations of information theory, especially if it was happening at neuron-scale.
Turing machines are countable. In some constructive settings, every real number is computable, as an axiom; those settings allow us to talk about the Turing machines which compute a particular real number.
reply