That proof does _not_ apply to FSMs

](I didn't want to go to this much work, but no one else has pointed

]this out, so here goes.)

It seems I didn't go to enought work. I mumbled off the criticism

that my Paradox function is recursive:

] Paradox = (Halt::E(Paradox)) -> CLoop ; CAccept

and then I made the mistake of sleeping on it. On further thought, it

seems that I have to add the restriction that the encoding function E

must be restricted to ensure that descriptions of the above sort are

finite. On even further thought, it seems that this restriction alone

takes the class of machines out of the FSMs.

Theorem: For any class of machines C on Sigma, if there is an

encoding E : C -> Sigma* such that all C-machines M of the form

M = M1::E(M) -> M2 ; M3

are finitely representable, then there are C-machines that can

recognize non-regular languages (which leads to the immediate that

the C-machine is not an FSA).

First, I have to add notation: CEmpty is the machine that accepts the

empty string and rejects all others. CReject is the machine that

rejects all strings. If the character c is Sigma, the machine c

accepts a single c and rejects any other string. The notation M1 M2

denotes the machine that accepts all strings that are the

concatenation of any string accepted by M1 with any string accepted by

M2. The notation M1 | M2 denotes a machine that accepts any string

accepted by either M1 or M2.

Proof: Assume that 0 and 1 are in Sigma. The C-machine

M = CEmpty | (0 (M:E(M) -> CAccept ; CReject) 1)

recognizes the language of n 0's followed by n 1's for any n >= 0.

This is not a regular language.

--

David Gudeman

noao!arizona!gudeman