Are humans Turing Machines?

[gusl]

I think so. It's almost required of believers in strong AI.

This afternoon, I had a colleague tell me that humans are superior to computers because we are not Turing machines, so we aren't subject to the halting problem. I told his arguments sounded a lot like Penrose's fallacious anti-strong-AI arguments.
We argued for about 10 minutes and then I gave up convincing him.

Crispin Cowan on the metaphysical implications of humans being Turing machines.

Boyer and Moore have a machine prove the Halting Problem

Comments

Re: hmm

[patrissimo.livejournal.com]

There was no miscommunication about a "deterministic automata". A DFA does indeed have memory, because it knows which of its states it is in. After all, what is memory if not a large set of possible "states" to be in? A DFA has log_2(N) bits of memory, where N is the number of states.

You could transform a computer program into a DFA as long as it only used a finite amount of memory known in advance, by letting each state in the DFA represent a complete description of the CPU registers, memory space of the program, current location of the PC, etc. The entire transition table (mammoth though it would be) could be precomputed and the DFA generated.

A DFA can't decide if a string fits 0^m 1^m because that requires log_2(m) bits of memory. If m can be arbitrarily large, then we just make m bigger than the number of states in the DFA, and the DFA can't keep track of the count of incoming 0's. Being forced to cycle in the state graph can be thought of as "running out of memory".

A Turing Machine with finite tape (or a PA with a finite stack) is just a DFA. It only has finite memory, and just like the computer program, we can "simulate" it with a DFA, each of whose states represents the complete state of the tape and the position of the head.

Since humans have only a finite amount of memory, how can we be Turing Machines? A TM can solve problems that take more memory than there are particles in the universe. We can't. We're just large DFA's...

Re: hmm

[gustavolacerda.livejournal.com]

I agree with you now. Thanks for refreshing my knowledge, and adding to my understanding.
It was counterintuitive for me that we can't decide 0^m 1^m.

A Turing Machine with finite tape (or a PA with a finite stack) is just a DFA. It only has finite memory, and just like the computer program, we can "simulate" it with a DFA, each of whose states represents the complete state of the tape and the position of the head.

That's an insight I should have had back when I studied Theory of Computation, but for some reason I didn't (I don't think the prof showed it either). I guess I was just sick of the whole thing.