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