Introduction to Artificial Intelligence

A universal Turing machine, then, is one that can be "given a program" that enables it to simulate a Turing machine: In fact, a universal Tm is theoretically equivalent to a general-purpose, discrete (or digital) computer, and the program one gives a digital computer is analogous to a descriptive string dT for some Turing machine T.

only essential difference between Turing machines and finite-state automata lies in the fact that a Turing machine is able to store its output on a potentially infinite tape and refer to it later

In fact, finite-state machines are only the building blocks of automata theory; they represent the simplest type of machine, one in which the future of an occurrence can depend on only a finite number of different "past histories," or states.

The mathematical theory that deals with functions that map one set of strings into another set of strings is automata theory;

There is no scientific guarantee that natural intelligence can be finitely described, either by our current scientific theories or by any mathematical description that could ever be developed—it may simply not be finitely describable.

So there are three possibilities that may hold if we are asked to describe something in a mathematical way: The thing may be finite, in which case presumably it is finitely describable (note 2–4); the thing may be infinite and yet finitely describable; the thing may be infinite and not finitely describable.

In other words, the fact that there is a mathematical way of describing some object means that it is finitely describable.

This does not imply the converse, that if a thing is finitely describable it is therefore mathematically describable

If intelligence is a finitely describable phenomenon, then it can theoretically be simulated on a (fast enough, big enough) computer.