Part 1: Automata and Languages

Chapter 1: Regular Languages

ITEC 420 - Section 1.4 - Non-Regular Languages

TM Parts


Accepting/Recognizing a String


Do More Tapes Give More Power?

Does Nondeterminism Give Extra Power?

Accepting/Recognizing a Language

Deciding a Language

Turing Recognizable and Turing Decidable Languages

Example 1

Example 2

A Hierarchy of Languages

A Language that is TR but not TD

Polynomials in 1 Variable

The Language of Polynomials with Integer Solutions

Polynomials in Several Variables

A TR but not TD Language

Hilbert's Problems and What is Computation?

What is Computation

Godel's Theorem (1931)

Church's Thesis

Turing Complete Languages: The End to Language Wars

Non TR Languages

ITEC 420 Course Page,
Last modified on