>> [
CNS
] >> [
Comp Sci Dept
] >> [
R J Botting
] >> [
CS546/646
] >> 11 [
Text Version
]
[
About
] [
Contact
] [
Grades
] [
Projects
] [
Submit
] [
Schedule
] [
Syllabus
] [Search
]
Session: [
01
] [
02
] [
03
] [
04
] [
05
] [
06
] [
07
] [
08
] [
09
] [
10
]
(11)
[
12
] [
13
] [
14
] [
15
] [
16
] [
17
] [
18
] [
19
] [
20
]
Thu Jun 8 13:02:56 PDT 2006
Contents
11
: Schedule
: Project
Notes
Standard Definitions
From Logic
11
Schedule
Date
Meet'g
Study
(2 pts)
Bring(5 pts)
Topic
(5 pts)
Notes
Wed May 3
10
Chapter 9 sections 9.1, 9.2
Ex
Undecidability & RE
Project1
(10 pts)
Mon May 8
11
Project2
(20 pts)

Turing Machines
Wed May 10
12
Chapter 9 section 9.3
Ex
Undecidability &
TM
Project
Working in a team of 3 or 4 people design, code, and test a simple Turing Machine simulator.
Notes
You may use any language that can be demonstrated in class.
You may choose any kind of user interface you like.
Your
TM
simulator does not have to have infinite memory capacity like a real
TM
.
Do the simplest thing that can possibly work.
Consult with me in my office hours.
Process
Start by thinking about the design and developing tests for your code...
(
Project1
): First deadline: bring a progress report to class and present it. Grading: pass/fail. Any running set of tests will pass.
(
Project2
): Second deadline: bring a report on the final status, present it, and hand in a hard copy for grading.
. . . . . . . . . ( end of section
12
)
<<
Contents  End
>>
Notes
(
Ex
): Do as many of the relevant exercises as you have time for. You may work in a team of upto 4 students and hand in one joint solution. Bring to class one written solution to an exercise. This must not be a solution to an exercise marked with an asterisk(*) to earn full credit. One of the authors will be invited to present the solution to the class  failure will loose points. Students taking CS646 must hand in the solution to an exercise marked with an exclamation mark(!) to earn full credit.
(
Study
): Read & think about the assigned items. Submit one question by selecting the submit button at the top of the web page. To earn complete credit you need to do this at least 90 minutes before the start of class. Hints. Read each section twice  once the easy bits and then the tough bits. Use a scratch pad and pencil as you read.
(
Topic
): To earn all the possible points you must: turn up on time, not leave early, present work when called upon, and take part in discussions.
Standard Definitions
FSA
::="Finite State Acceptor/Automata", a theoretical machine with a finite set of states.
ND
::="Nondeterministic", a machine that can try out many possibilities and always guesses the right choice. Note: For a given problem a
ND
solution is simpler and easier to understand than a deterministic one. We study
ND
machines to discover how to use them as highlevel designs for more complicated deterministic machines. Plus it's fun.
PDA
::="Push down Automata", a machine with a finite control and a single stack for remembering intermediate data. Kind of like half a
TM
.
RJB
::=
The author of this document
, [
../index.html
]

RJB
="Richard J Botting, Comp Sci Dept, CSUSB".
Schedule
::= See
http://www.csci.csusb.edu/dick/cs546/schedule.html
.
Search
::= See
http://www.csci.csusb.edu/dick/cs546/lookup.php
.
Syllabus
::= See
http://www.csci.csusb.edu/dick/cs546/syllabus.html
, and also see [
syllabus.html
] (my generic syllabus).
TBA
::="To Be Announced".
TM
::="Turing Machine".
NTM
::="Nondeterministic Turing Machine".
nondeterministic
::="A machine that can make choices as it runs and accepts an input iff any sequence of choices leads to acceptance."
DTM
::="Deterministic Turing Machine".
runtime
::=
run_time
,
run_time
::="The number of steps a TM takes before it halts when start on a given input".
complexity
::="The largest
run_time
for any word with a given length" , usually expressed as an assymptotic (BigO) formula.
P
::@problem=
class of problems that a
DTM
can compute in
polynomial_time
.
NP
::@problem=
class of problems that a
NTM
can compute in
polynomial_time
.
polynomial_time
::=
An algorithm/TM is said to halt in polynomial time if the number of steps given n items of data is less than O(n^c) for some constant c
.
From Logic
LOGIC
::= See
http://www.csci.csusb.edu/dick/maths/logic_25_Proofs.html
(
LOGIC
)

(
ei
):
Existential instantiation  if P is true of something then we can
substitute a new variable for it.
(
LOGIC
)

(
eg
):
existential generalization  if P is true of this thing then
it is true of something!
(
LOGIC
)

(
given
):
a proposition that is assumed as part of a Let...End Let argument.
Typically
if A and B and C then D
starts with assuming A,B, and C are
given
. They are called the hypotheses.
(
LOGIC
)

(
goal
):
a proposition that we wish to prove. Typically the part after
the
then
in an
if...then...
result. This is called the conclusion.
(
LOGIC
)

(
def
):
By definition of a term defined above.
(
LOGIC
)

(
algebra
):
Either by using well known algebraic results, or by
use a series of algebraic steps.
(
LOGIC
)

(
RAA
):
Reduce to absurdity. The end of a Let/Po/Case/Net that
establishes the negation of the last set of assumptions/hypotheses.
End