ITEC 420
What This Course is All About!
ITEC 420 Topics
- ITEC 420 Covers 4 topics
- Models of Computation
- Languages
- Theoretical Limits of Computation
- Practical Limits of Computation
ITEC 420 Topics
- Models of Computation
- Languages
- Theoretical Limits of Computation
- Practical Limits of Computation
Models of Computation: An Example
- A simple model: Finite Automata (FA)
- Problem: Design a simple computer that checks if a string is valid
- Valid strings: 0 or more a's followed by a single b
- Example valid strings: b, ab, aab, aab, aaab, ...
- Example non valid strings: a, aa, ba, aba, ...
- Usually write strings without quotes
- Solution:
- Draw it on board
- How it computes:
- Start in state 1
- One transition per input symbol
- Accept if in state 2 at end of input
- Example strings: ab, aab, b, a, aba
Terminology: Machines and Automata
- Automata is plural of automaton
- An automaton is a self operating machine
- We use automata and machine(s) interchangably
Terminology: Finite Automata
- Alternate names for FA
- aka Finite State Automata (FSA)
- aka Finite State Machines (FSM)
Other Models of Computation
- We will study 3 main models
- From simple to complex:
- Finite Automata
- Push down Automata (FA plus a stack)
- Turing Machine (FA plus a tape)
- Named after mathematician Alan Turing
- There are a few other models
- Deterministic and non-deterministic
- Generalized Nondeterministic Finite Automata
Computational Power of Models
- More complex machines allow more powerful computations
- Examples from compilers:
- FA: recognize tokens (ie words of program, but not structure)
- PDA: recognize syntax (ie structure of program)
- Turing Machines: Most powerful
- Can compute anything that can be computed!
- By any computer and any language!
- This is the Church-Turing Thesis
Abstract Models
- Our models are abstract
- Abstract means
- Pay attention to certain details
- Ignore other details
- Pay attention to:
- Machine states
- How machine responds to input
- Ignore:
- Physical implementation
- No program (in traditional sense)
Defining Models
- Models can be defined in 2 ways:
- Informally: Diagrams, for example
- Formally: mathematical sets and functions
Formal Definition of Our Example
- Our example uses these sets, etc:
- Input characters: {a, b}
- States: {1, 2, 3}
- Transition function:
- Initial State: 1
- Accepting states: {2}
- Must also define computation appropriately
ITEC 420 Topics
- Models of Computation
- Languages
- Theoretical Limits of Computation
- Practical Limits of Computation
What is a Language?
- A language is a set of strings!
- Repeat: A language is a set of strings!
- Example languages:
- 0 or more a's followed by a single b
- all strings with an equal number of a's and b's
- Example strings in this language: ...
- Strings of length 2, 4, 1, 3, 0?
- Example strings NOT in this language: ...
- Strings of length 2, 4, 1, 3, 0?
Defining Languages
- A language is a set of set of string
- How can we define that set?
- Ways of defining strings:
- Words: 0 or more a's followed by a single b
- Examples: {b, ab, aab, aaab, ...} (any problems with this?)
- Set notation: {anb | n >= 0} (an must be defined)
- Regular Expressions: a*b
- Grammars:
S -> aS
S -> b
- We will study regular expressions and grammars later
Equivalence of Machines and Languages
- We will learn that certain kinds of machines define certain kinds of languages
- Kinds of languages we will learn about:
- Regular languages
- Context free languages
ITEC 420 Topics
- Models of Computation
- Languages
- Theoretical Limits of Computation
- Practical Limits of Computation
Theoretical Limits of Computation
- Can everything be computed?
- What about: What should I have for supper?
- Problem is not precisely defined
- Question: Can every precisely defined language be computed?
- We will prove that
- There are precisely defined languages (ie sets of strings)
- That have no machine that computes them!!!
- This is a limit of computation
- That is, it's a limit of what can be computed
- Anywhere
- At any time
- By any kind of machine with any language
The Halting Problem and Diagonalization
- One non-computable problem is the Halting Problem
- Can you write a program that can check any program X to see if X halts
- Answer: No
- One of the main techniques for proving the halting problem is diagonalization
- We will look at it in a few minutes
ITEC 420 Topics
- Models of Computation
- Languages
- Theoretical Limits of Computation
- Practical Limits of Computation
Practical Limits of Computation
- What problems can be computed on real machines
- In a practical amount of time
- What problems can be computed on real machines, but
- NOT in a practical amount of time
Complexity Theory
- We will study two problem classes: P and NP
- Roughly we can say:
- Problems in P have known practical solutions
- Problems in NP may have practical solutions, but no one knows
- The Million Dollar Question (literally): Is P = NP???
- Do the problems in NP have practical solutions?
- No one knows!
Course Outcomes
- Demonstrate an ability to understand and apply mathematical concepts.
- Describe, analyze, and design language generators and recognizers including
context free grammars and both deterministic and non-deterministic finite automata,
pushdown automata, and Turing machines.
- Use a Pumping Lemma to prove that a language is not in a given class.
- Explain the Church-Turing Thesis and its significance.
- Describe example unsolvable problems and outline how a problem can be shown to be unsolvable.
- Define the classes P, NP, NP-Complete and explain their significance.
Why Study Theory of Computation
- Lots of applications
- Programming language design and implementation
- String processing
- Cryptography
- Ability to recognize hard problems
- Broaden your understanding of computers
- Improve ability for abstraction
- Exposure to beautiful ideas
- Preparation for Graduate School