You interpret 'accepting a string' as meaning:

Start the TM with the string on the tape (and nothing else)

If the TM halts with this input, then we say it "accepted the string"

The "language recognized by some particular TM" consists of those strings that it accepts.

A major result of formal language theory is that TMs can recognize any language which is describable by any (re-write) rules whatsoever.

Thus anything describable by re-write rules is TM-computable.

Type 0: Unrestricted re-write rules (unrestricted substitution, allows for contraction). Rules of the form:

Type 1: Context sensitive rules. Rules of the form:

ÏAÁ ƒ ÏwÁ (w not empty)

S ƒ ø

Type 2: Context free rules. Rules of the form:

A ƒ w (w not empty)

S ƒ ø

Type 3: Regular (linear) rules. Rules of the form:

A ƒ aB (for right linear)

A ƒ a

S ƒ ø

Where: A Œ N ‰ S; Ï,Á,wŒ(N‰T)*; BŒN; aŒT.

To each grammar type there corresponds the type of language which can be produced by that sort of grammar:

To Type 0 grammars, any RE set of strings (a completely unconstrained set, basically). It was proved in the 1970 time frame that the Chomskean transformational grammars of the time could generate any RE set of strings, and therefore were equivalent to TMs. People thought this was bad.

To Type 1 grammars, there corresponds the class of context-sensitive languages.

To Type 2 grammars, there corresponds the class of context-free languages.

To Type 3 grammars, there corresponds the class of regular languages.

We've already noted that TMs can recognize any Type 0 language, and hence are equivalent to unrestricted rewrite rules…and hence are equivalent to RE sets.

Similar correspondences exist with the other grammar types:

To Type 3 grammars, there corresponds the notion of "a finite state automata"…sometimes called Markov machines (which is a particular way of conceptualizing them).

To Type 2 grammars, there corresponds "pushdown stack automata"

To Type 1 grammars, there corresponds the notion of a "linear bounded tape TM"

All the relations indicated are proper inclusions….the class of unrestricted rewrite languages properly includes the class of context sensitive languages, which properly includes the class of context free languages, which in turn properly includes the class of regular languages.

Therefore there is a sense in which the Type 0 grammars are "stronger" than the Type 1 grammars, which are "stronger" than the Type 2 grammars, which in turn are "stronger" than the Type 3 grammars.

And equally, there is a sense in which TMs are "more powerful" than linear-bounded tape automata, which are "more powerful" than pushdown stack automata, which in turn are "more powerful" than finite state machines.

Question for Cognitive Scientists who believe that the human mind is (or: is adequately modeled by) an abstract machine: what type of machine is it?

Gödel proved two theorems about "System P"…which was Alfred Whitehead & Bertrand Russell's Principia Mathematica with further axioms from Peano Arithmetic (usually called PA) added.

The two theorems were:

1. If P is consistent, then there exists a sentence Í (of P) such that neither Í nor ~Í is provable (in P).

[This is problematic, since Í is a statement about the numbers (like, 2+2=4 or 25*15<300). Therefore, Í should either be true or be false…and maybe even necessarily true or necessarily false. This state of affairs also cannot be changed by just finding Í and adding it (or its negation) as a new axiom, for then there will be another Í´ for which neither it nor its negation is provable in this new system…assuming it's still consistent.]

2. If P is consistent, then cons (a statement of P which "says" that P is consistent) is not provable in P.

[This is problematic because we know that arithmetic is consistent…but we can never prove it. Furthermore, we can't just add this as a new axiom, because then there will be another cons´ (which is a statement of this new system, saying that the new system is consistent) which is not provable in the new system.]

People have made much out of this theorem. I'm going to make this into a term paper question, and you can do the research on it later if you want. But the main authors who have thought that it really did prove that machines cannot think are:

Lucas (in 1960s and 1970s articles)

In Lucas' version, he asks you to imagine that you are a TM (a UTM?). He then proves to you that you cannot prove your own consistency…but that you can "see" that you are in fact consistent.

There are also plenty of mathematicians who also seem to believe the conclusion….maybe Gödel himself, Fefferman, …

They all think we have some special "mathematical knowledge" which is different from "empirical knowledge".

Does this sound right? Are we even sure that our beliefs are closed under Modus Ponens?

An elementary intro to Gödel's incompleteness theorems (thanks, Smullyan!)

Example: suppose we have a computing machine that prints out various expressions composed of the five symbols in our language:

~ P N ( )

an expression is any finite nonempty string of these five symbols

an expression X is called printable if the machine can print it. (and we assume that the machine will eventually print anything that it can print)

the norm of an expression X is the expression X(X). [so, the norm of P~ is P~(P~) ]

a sentence is defined (X is any expression)

P(X)

P N(X)

~ P(X)

~ P N(X)

Informally, P means "printable"; N means "the norm of"; and ~ means "not".

Define P(X) to be true if and only if (iff) X is printable

So, P N(X) is true iff the norm of X is printable

We have now a perfectly precise definition of what it means for a sentence to be true, and an interesting case of self-reference:

The machine is printing out various sentences about what the machine can and cannot print…and so it is describing its own behavior!

[It somewhat resembles a self-conscious organism, and that's why such computers are of interest in AI]

We are given that the machine is completely accurate in that all sentences printed by the machine are true. So, for example, if the machine ever prints P(X), then X really is printable (X will be printed by the machine sooner or later).

Also, if P N(X) is printable, so is X(X) [the norm of X].

Now, suppose X is printable. Does it follow that P(X) is printable? Now necessarily. If X is printable, then P(X) is certainly treu, but we are not given that the machine is capable of printing all true sentences but only that the machine never prints any false ones. (Every sentence that is printable by the machine is true).

Is it possible that the machine can print all true sentences??

[Find a true sentence that the machine cannot print]

[Hint: find a sentence that asserts its own non-printability – i.e., one which is true iff it is not printable by the machine.]

[Answer: ~ P N(~ P N). By definition of true this sentence is true iff the norm of ~ P N is not printable. But the norm of ~ P N is the very sentence ~ P N(~ P N) !!

And so the sentence is true iff it is not printable. This means that either the sentence is true and not printable, or it is printable and not true.

The latter alternative violates the given hypothesis that the machine never prints sentences that are not true.

Hence: The sentence must be true, but the machine cannot print it !

Of course, instead of having a machine that prints various expressions in the five symbols, we could have talked about a mathematical system that proves various sentences in the five symbols.

We would then say that P stood for provability in a mathematical system rather than printability by our machine.

Then, given that the system is wholly accurate (in that, false sentences are never provable in it), the sentence ~ P N(~ P N) would be a sentence that is true but not provable in the mathematical system.

Further observe: The sentence P N(~P N) is false [since its negation is true]. Hence it is also not provable in the system, since the system is accurate.

And so the sentence

P N(~P N)

is an example of a sentence that is undecidable in the system – i.e., neither it nor its negation is provable in the system.

A variant using Gödel numbering

Another machine that prints out expressions composed of the following five symbols:

~ P N 1 0

And we represent the natural numbers in binary notation (as strings of 1's and 0's).

To each expression we assign a number called the Gödel number of the expression. We use the following scheme:

The individual symbols ~ P N 1 0

Are assigned 10 100 1000 10000 10000 respectively

The godel number of a compound expression is obtained by replacing each symbol by its Gödel number – P N P has Gödel number 1001000100.

The norm of an expression is the expression followed by its Gödel number——the norm of P N P is the expression PNP1001000100.

A sentence is an expression of the form

P X P N X ~ P X ~ P N X

Where X is any number (in binary notation)

P X is true iff X is the Gödel number of a printable expression.

P N X is true iff X is the Gödel number of an expression whose norm is printable

P N X is true iff X is the Gödel number of an expression whose norm is printable

~ P X is true iff P X is not true (ie., X is not the Gödel number of a printable expression)

We are given that the machine never prints a false sentence. Problem: Find a true sentence that the machine cannot print.

Answer: ~ P N 101001000

A Provability Predicate P for a system S has the following three conditions hold, for all sentences X and Y in S…where *X* means "the Gödel number of X":

1. If X is provable in S, then so is P(*X*)

2. P(*(XƒY)* ƒ (P(*X*) ƒ P(*Y*)) is provable in S

3. P(*X*) ƒ P(*P(*X*)*) is provable in S

If a machine is (a) strong enough to "code up arithmetic" and thereby use Gödel numbering, and if it has a Provability Predicate, then there will be true sentences it cannot prove.

Does this show that people are not machines of this sort?

The Löwenheim-Skolem Theorem:

Is a group of results that concern the size of domains of interpretation of sentences in FOL. They typically have the form:

If there is an interpretation with [semantical] property X,

then there is an interpretation with [semantical] property

X which has domain of size Y.

It is easy to concoct examples (sets of sentences) that require an infinitely large domain for them all to be true.

There is also a question of whether it is possible to concoct an example (set of sentences) that require a non-denumerably infinite domain for them all to be true?

Skolem's original theorem answers this negatively:

We can describe an interpretation I that contains a non-denumerable number of elements (and maybe even use it as a model for the real numbers). But there is no set of FOL sentences that require anything more than a denumerable sub-domain of I to make them all true.

This result has been called "paradoxical". There exist certain interpretations in which a certain sentence (that seems to say that non-enumerably many sets of natural numbers exist) is true…even though the domains of these interpretations contain only enumerably many sets of natural numbers. [And furthermore, the predicate "is a set of natural numbers" is true just of the sets of natural numbers in the domains.]

Most "explanations" of the paradox distinguish between what's true about the interpretation and what's truly sayable within the interpretation.

For example, although it can be proved that a non-denumerable domain cannot be enumerated, this proof cannot be carried out within the sentences that describe the domain.

All this has led some philosophers & cognitive scientists (e.g., Putnam) to propose [what they call] "internal realism"….