I've mentioned that one can't write algorithms to solve the
Entscheidungsproblem, the word problem, the Diophantine equation
problem, the problem of whether any set of polygons will tile the plane,
or the topological equivalence of manifolds in 4 dimensions or more. To
anticipate what I'm going to say later, Turing showed that all computers
were equivalent to each other, and to an ``ideal'' computer called a
Turing machine. If an algorithm doesn't exist for one computer, it won't
for any. So I'll say in future that problems like the above, for which
there exists no algorithm, are *non Turing-computable*. Sometimes,
I'll say *non-computable* for short. Other problems are
Turing-computable, or computable for short.

I'll say that any computer which is equivalent in power to a Turing
machine is *Turing equivalent*. This covers all digital computers.
It is also an upper limit on connectionist systems. Some (e.g. the
linear associator) may have less power than a Turing machine, in that
they can't compute something it can. But none have more power.

No-one has yet built a computer that can compute more than a Turing machine can. But some people believe that one could do so using quantum effects, and I'll talk about that next week. Some people, such as Penrose, also believe that the brain uses such effects, and hence can solve non-Turing-computable problems.

Wed Feb 14 23:47:23 GMT 1996