COMP 455 Links
COMP 455 Links
Spring 2010
SYLLABUS
REGULAR EXPRESSIONS
Perl 6 Regular Expressions
Introduction to PERL
The UNIX "GREP" Utility
Using Regular Expressions
Mastering Regular Expressions
A Tao of Regular Expressions
Wikipedia Article on Regular Expressions
FINITE AUTOMATA
Zero Counter Automaton
Parity Automaton
Universal Automaton
Java Formal Languages and Automata Package
Nontraditional Applications of Automata Theory
Protein Sequence Similarity Search Programs
PRACTICE FOR EXAM 1
Practice Exam 1 (pdf)
Practice Exam 1 (latex)
Practice Exam 1 (word)
Practice Problems from the Text
PRACTICE FOR EXAM 2
Practice Exam 2 (postscript)
Practice Exam 2 (latex)
Practice Exam 2 (pdf)
Practice Exam 2 (word)
Practice Problems
Solutions to Practice Problems
Practice Problems from the Text
PRACTICE FOR EXAM 3
Practice Exam 3 (pdf)
Practice Problems from the Text
TURING MACHINES
A Universal Turing Machine
Bounds on the Busy Beaver Function
Proof of Uncomputability of the Busy Beaver Function
References on the Busy Beaver Function
Turing Kara
TuringKara manual in English
Kara Java archive; right click, save to disk with .jar extension, then double click.
PHILOSOPHICAL ISSUES
Discussion of Goedel's theorem and other incompleteness results
Discussion of unsolvability of Hilbert's tenth problem
Mathematics and the Mind
Minds, Machines, and Goedel
The Goedelian Argument
Limitations of Self Knowledge
Minds, Machines, and Mathematics
The Non-Algorithmic Character of Human Consciousness
HOMEWORK
Homework 1
Homework 2
Homework 3
Homework 4
Homework 5
Homework 6
Homework 7
Homework 8
Homework 9