There’s a real vs theoretical distinction. Turing machines are defined as having infinite memory.
Running out of memory is a big issue that prevents computers from solving problems that Turing machines should be able to solve.
The halting problem, a bunch of problems involving prime numbers, a bunch of other weird math problems are all things that can’t be solved with Turing machines. They can all sort of be solved in some circumstances (eg A TM can correctly classify many programs as either halting or not halting but there are a bunch of edge cases it can’t figure out, even with infinite memory).
From what I remember, most researchers believe that human brains are Turing Complete. I’m not aware of any class of problem that humans can solve that we don’t think are solvable by sufficiently large computers.
You’re right that Quantum Computers are Turing Complete. They’re just the closest practical thing I could think of to something beyond it. They often let you knock down the Big Oh relative to regular computers. That was my point though. We can describe something that goes beyond TC (like “it can solve the halting lemma”) but there don’t seem to be any examples of them.
I’m not aware of any class of problem that humans can solve that we don’t think are solvable by sufficiently large computers.
That is a really good point…hrmmm
My conjecture is that some “super Turing” calculation is required for consciousness to arise. But that super Turing calculation might not be necessary for anything else like logic, balance, visual processing, etc
However, if the brain is capable of something super Turing, I also don’t see why that property wouldn’t translate to super Turing “higher order” brain functions like logic…
We certainly haven’t ruled out the possibility that the human brain is capable of some sort of “super Turing” calculations. That would lead me to 2 questions;
Can we devise some test to show this? If we expand our definition of “test” to include anything we can measure, directly or indirectly, through our senses?
What do we think is the “magic” ingredient that allows humans to engage in “super turing” activities, that a computer doesn’t have? eg Are carbon compounds inherently more suited to intelligence than silicon compounds?
There’s a real vs theoretical distinction. Turing machines are defined as having infinite memory. Running out of memory is a big issue that prevents computers from solving problems that Turing machines should be able to solve.
The halting problem, a bunch of problems involving prime numbers, a bunch of other weird math problems are all things that can’t be solved with Turing machines. They can all sort of be solved in some circumstances (eg A TM can correctly classify many programs as either halting or not halting but there are a bunch of edge cases it can’t figure out, even with infinite memory).
From what I remember, most researchers believe that human brains are Turing Complete. I’m not aware of any class of problem that humans can solve that we don’t think are solvable by sufficiently large computers.
You’re right that Quantum Computers are Turing Complete. They’re just the closest practical thing I could think of to something beyond it. They often let you knock down the Big Oh relative to regular computers. That was my point though. We can describe something that goes beyond TC (like “it can solve the halting lemma”) but there don’t seem to be any examples of them.
That is a really good point…hrmmm
My conjecture is that some “super Turing” calculation is required for consciousness to arise. But that super Turing calculation might not be necessary for anything else like logic, balance, visual processing, etc
However, if the brain is capable of something super Turing, I also don’t see why that property wouldn’t translate to super Turing “higher order” brain functions like logic…
We certainly haven’t ruled out the possibility that the human brain is capable of some sort of “super Turing” calculations. That would lead me to 2 questions;
Can we devise some test to show this? If we expand our definition of “test” to include anything we can measure, directly or indirectly, through our senses?
What do we think is the “magic” ingredient that allows humans to engage in “super turing” activities, that a computer doesn’t have? eg Are carbon compounds inherently more suited to intelligence than silicon compounds?