[FOM] Formation Rules
urquhart at cs.toronto.edu
Fri Oct 20 13:05:21 EDT 2006
John Corcoran asked:
" I would like to know when logicians started thinking of formal
languages as subsets of the set of finite strings over a finite
alphabet, which of course is what they are.
This conception of what formal languages are is not so obvious, not if
"what they are" is meant in any but a very weak sense."
An early source for this idea is in C.I. Lewis's " A Survey of Symbolic
Logic" published in 1918. In his sixth chapter, Lewis contrasts the logistic
method of Whitehead and Russell with what he calls a "heterodox" view of the
nature of mathematics and logistic.
Lewis presents his view of the logistic method in the
following striking definition:
A mathematical system is any set of strings of recognizable
marks in which some of the strings are taken initially and the
remainder derived from these by operations performed according to
rules which are independent of any meaning assigned to the marks.
and he goes on to present the propositional calculus of Principia Mathematica
as a mathematical system in his sense.
This Chapter 6 of Lewis's Survey had a very strong influence on Emil Post.
Unfortunately, when the book was reprinted as a Dover paperback in 1960,
Lewis chose to omit this chapter. Consequently, this historically influential
chapter is now rather hard to access.
More information about the FOM