Projects and Assignments in Pure Mathematics
Formal Machines
This project may examine the following kinds of machine:
finite automata with or without silent moves, with or without output,
deterministic or non-deterministic, pushdown automata, linear bounded
automata, Turing machines, register machines. The idea is to compare
and
contrast these types of machine in terms of their computing power, and
which
'languages' they will recognize. There is plenty of scope for use of
examples,
as well as studying beautiful characterization theorems.
Books
J H Conway, Regular algebra and finite machines, Chapman and Hall,
1971.
S B Cooper, Computability theory, Chapman Hall, 2003.
N Cutland, Computability: an introduction to recursive function theory,
CUP, 1980.
J E Hopcroft and J D Ullman, Introduction to automata theory,
languages, and
computation, Addison-Wesley, 1979.
J K Truss Discrete Mathematics for Computer Scientists, 2nd edition,
Pearson,
1999.
Pure projects homepage