Week 1: to do
Mathematics 3670: Computer Systems
Introduction
Dr. Andrew Mertz
Mathematics and Computer Science Department
Eastern Illinois University
Fall 2012
The big picture
What
Read Chapter 1
When
this week
Read Lab 1 handout
before Thursday
Determine Lab 1 Turing
machine snapshots
Design Turing machine
for halving
Complete Lab 1
before Thursday
Submit Lab 1 work
on/before next Thursday
Problems
Algorithms
Language
Machine architecture (ISA)
Microarchitecture
Circuits
Devices
Bottom level is most basic; upper levels appear most complex
We will study this hierarchy from the bottom up
Key idea: how is level N ` 1 implemented given level N ?
Ultimate aim understand how the top level is achieved:
no magic allowed!
Begin with a problem statement
What are the inputs?
What are the desired outputs?
What is the relationship between inputs and outputs?
this Thursday
A hierarchy
Complex systems can be organized as a hierarchy of
abstractions
Problem solving with computers
before Thursday
A simple problem
Input: A non-negative integer n
Output: n mod 3
To design an algorithm for this problem, we need to know:
Design an algorithm, which will transform inputs to outputs
what primitive operations are available
How do we express the algorithm?
Ultimately, we want the algorithm to become a well-defined
pattern of electrons flowing within a physical computer
what abstraction level is appropriate
Depending on the abstraction level, we may also need to be aware
of data representation
The Turing machine
The Turing machine: basic ingredients
A tape, divided into squares infinite in both directions
Proposed in 1936 by English mathematician Alan Turing
A read/write head which can inspect and change the contents
of one square on the tape
Can be used to formalize the idea of algorithm
A finite control unit which remembers the state
Is simple to describe
A set of states with one initial state
Like modern computers, operates at a very basic level: any
one step within a computation doesnt do very much
Turing machine actions
A subset of states called final states
A finite table of actions which controls how the machine
makes one computational step
Turing machine actions
Any one action of the Turing machine is described by five
components:
current state
current symbol
The action pq, 0, 1, q 1 , Lq can be viewed as an edge in a directed
graph:
0, 1, L
symbol to write
next state
direction to move read/write head: left, right, stay
For example, pq, 0, 1, q 1 , Lq tells the machine if in state q the
read/write head is scanning the symbol 0, then overwrite it with
the symbol 1, switch to state q 1 and move the read/write head one
step to the left
Turing machines: one computation step
0, 1, L
q
We can describe a Turing machine with a collection of actions like
these, giving us a labeled, directed graph
Computing functions with Turing machines
q1
q0
0 1 1
q
1 1 1
q1
q1
f pq
qf
Back to the mod 3 problem
A Turing machine solution for the mod 3 problem
0 : l, R
q1
We will represent n in unary
For input 35, place 35 consecutive 0s on the tape
We want to end up with 35 mod 3 2, i.e., 2 consecutive 0s
Division by 3 can be accomplished by repeated subtraction
l : 0, L
q2
q3
l : 0, S
0 : l, R
l : 0, S
0 : l, R
Challenge: what states and transitions are needed?
Lets think about it. . .
l : l, S
q0
Simulating a Turing machine
q4
Understanding the mod 3 Turing machine
q1
0 : l, R
0 : l, R
l : 0, L
q2
l : 0, S
0 : l, R
Live demo of JFLAP
l : l, S
q0
q3
l : 0, S
q4
The q0 , q1 , q2 cycle subtracts 3 on each complete loop
q0 so far, we have removed 3t zeros
q1 so far, we have removed 3t ` 1 zeros
q2 so far, we have removed 3t ` 2 zeros
q2 q3 q4 writes 00, then halts
q1 q4 writes 0, then halts
q0 q4 writes l, then halts
Turing machines as black boxes
Universal computational device (Turing, 1936)
T mod 3 does one task and one task only
If you want to perform some other task, you need a different
machine
n
T mod 3
n mod 3
Black box view is an essential abstraction:
Hides inessential detail
Allows for understanding of big picture
Could we design one machine that can do the work of any
other machine?
Yes! This is the machine we call U the universal machine
M, x
output of M , given x
U simulates what M would do a programmable computer!
Turings thesis
Important idea #1 (textbook)
If an algorithm exists for some problem, there is an
equivalent Turing machine
All computers (big, small, fast, slow, . . . ) are capable of
computing exactly the same things, given enough time
and enough memory
Turings work provides a foundation for understanding the limits of
computation what is possible to compute and what is
impossible to compute
Important idea #2 (textbook)
Problems we wish to solve with a computer are stated in
some natural language, such as English. Ultimately, these
problems are solved by electrons running around inside
the computer. To achieve this, a sequence of systematic
transformations takes place. At the lowest levels, very
simple tasks are being performed.
Problem statement
The hierarchy, revisited
Problems
Algorithms
Language
Machine architecture (ISA)
Microarchitecture
Circuits
Devices
The algorithm: essential ingredients
Stated in a natural language, like English
Some number of inputs
We must avoid any ambiguity
Some number of outputs
Misunderstandings at this level will cause many issues later in
the development, increasing development cost, delaying
completion
Definiteness property: each step must be precisely defined
Obtaining an accurate specification of the problem is often
difficult
Finiteness property: the algorithm, when followed, must
terminate after a finite number of steps
Effectiveness property: each step must be something that can
be carried out by a person in a finite amount of time
Definiteness you be the judge
Suppose m and n are two arbitrary integers; positive, zero, or
negative
We are devising an algorithm that uses integer division,
with quotient and remainder; one step is:
let k be the remainder of m n
For definiteness, we need a precise definition of the action
Do we have that?
Finiteness you be the judge
Effectiveness you be the judge
Suppose we are devising an algorithm which uses floating
point arithmetic; one step is:
if there are 7 consecutive 3s in the decimal expansion of
then . . .
For effectiveness, each step must be something that can be
basic enough to be carried out by a person
completed in a finite amount of time
Do we have that?
From algorithms to programs
Suppose we are computing with exact, rational arithmetic
Let x be 1/7
Determine m and d1 , d2 , . . . , dm so that
0.d1 d2 . . . dm x
To implement an algorithm, we need a programming language
For finiteness, each step must terminate after some finite
number of steps
High level machine independent
High level: Java, C++, C, COBOL, FORTRAN, Python, Perl,
Prolog, etc.
Low level: Assembly language
Low level tied to a specific architecture
Do we have that?
The ISA Instruction Set Architecture
Microarchitecture
Ultimately, programs are expressed as patterns of 0s and 1s:
machine language
Translators (compilers and assemblers) perform conversion,
producing machine language from higher levels
ISA specifies:
instruction set (what operations are possible?)
data types (e.g., integer vs. floating point, range and precision)
addressing modes (how is an operand located in the memory?)
Typical ISAs: Intel x86, HP PA-RISC, Sun Sparc, ARM,
Motorola 68k, etc.
microarchitecture: implementation of an ISA
To add x to y requires lower level details, register transfers,
etc.
There can be multiple implementations of an ISA
Logic circuits
Fundamental building blocks: AND, OR, NOT
Very simple: one bit operands
Use these building blocks to create ALUs, memories, etc.
Device level
Technologies: CMOS, NMOS, GaAs, etc.
Solid-state physics, electrical engineering
