- People
- Course description
- Lecture slides and notes
- Tutorial Exercises
- Assignments
- General Information & Other Resources

Lecturer: | Michael Fourman | mfourman@inf.ed.ac.uk |

Teaching Assistants: | ??? | ??? |

The goal of this course is to introduce you to computational thinking — using computational models to describe and reason about systems that change through time. We focus on finite-state systems and propositional logic.

Finite state machines provide a simple model of computation that is widely used, has an interesting meta-theory and has immediate application in a range of situations. They provide an essential underpinning for your future study of more general computational models, across the whole of Informatics.Propositional logic, is used to describe and reason about finite state systems. It provides a basis for later study of more general logics used to specify and reason about Informatic systems.

- Informatics looks at the world in terms of information.

Nature is, perhaps, infinitely complicated, but we often use abstract models of natural systems based on a finite amount of information.

The first part of this course deals with such models, how we can speak about the states of such systems, using propositional logic.

For example, a weather report describes the state of the weather by reporting a finite number of attributes. The philosophers have only interpreted the world, in various ways; the point is to change it.

In the second part of the course we model change. Many systems in nature change continuously. Our second abstraction is to consider a discrete series of time steps, and to focus on how the state of our system changes from one step to another, without worrying about the details of what happens in between.

For example, in describing a game of chess we focus on the state of the board before and after each move, but pay no attention to the way the players move their pieces.- A brief introduction of computation as a process and a method of modelling behaviour. Discussion of the advantages of moving to simple models that are appropriate for restricted classes of tasks. Discussion of the importance of correctness of computational procedures, and how logic can be used to reason about correctness.
- Reasoning: Propositional logic, its connectives and the meaning of those connectives in terms of truth tables. The concepts of satisfiability, validity and proof. The relationship between a proof and the validity of an implication in terms of truth tables.
- Computation: the definition as acceptor and transducer, deterministic/non deterministic machines, regular expressions, operations on FSMs, discussion of formal limits, how good are FSMs as a model of interactions.
- Applications/Modelling: simple examples drawn from a number of domains, design issues, using operations on FSMs to structure solutions, more complex examples: dialogue systems, controllers, digital watch, regular expressions and pattern matching. Application areas such as robotic controllers.
- Engineering: how do we specify, test and debug FSM's, design by decomposition, concurrency, size of machines.
- Using Logic to describe change. The Stanford Research Institute Problem Solver (STRIPS) and elementary planning.
- Tools: examples of logic/FSM based tools in system building.

The main reference for this course is *Foundations of Computer Science* by Aho and Ullman.
This book has been taken out of print by W. H. Freeman. You may be lucky and find a used copy,
e.g. on Amazon,
but it is freely available for download on the web :-)

As a secondary reference, I suggest you purchase Kozen's
*Automata and Computability*.
The second half of the course will follow Kozen quite closely.
Although you will only be using the first 50 pages or so for this course,
this book is also used in Inf2.

- Logic notes
- Lecture slides: Lecture 1, Lecture 2, Lecture 3, Lecture 4, Lecture 5, Lecture 6, Lecture 7.
- Logical Equivalences

- FSM notes: Section 1, Section 2, Section 3, Section 4, Section 5, Section 6, Section 7.
- Lecture slides: Lecture 1, Lecture 2, Lecture 3, Lecture 4, Lecture 5, Lecture 6, Lecture 7. Lecture 8.

- Week 3 (29 September - 3 October) Tutorial 1: Propositional Logic: An Introduction [Solutions]
- Week 4 (6 - 10 October) Tutorial 2: Propositional Logic: Truth Tables [Solutions]
- Week 5 (13 - 17 October) Tutorial 3: Propositional Logic: Sequent Calculus [Solutions]
- Week 6 (20 - 24 October) Tutorial 4: Propositional Logic: Resolution [Solutions]
- Week 7 (27 October - 311 October) Tutorial 5: Computation: Introduction to Finite State Machines [Solutions]
- Week 8 (3 - 7 November) Tutorial 6: Computation: Non-Deterministic FSMs and FSM Composition [Solutions]
- Week 9 (10 - 14 November) Tutorial 7: Computation: Regular Expressions [Solutions]
- Week 10 (17 - 21 November) Tutorial 8: Computation: Subset Procedure [Solutions]
- Week 11 (24 - 28 November) Tutorial 9: Revision [Solutions]new!

- The following assignment is due for submission to the Informatics Teaching Organisation (level 4 of Appleton Tower) by noon 15th of November. [Assignment]
- Guide to Standard Answers (and Marking Scheme) [Answers]new!

- Past papers for all Informatics courses and modules, organised by year. Search through each year to find available Inf1 Computation and Logic past papers.
- Wikipedia is a good source for many topics, such as,
- Click here
for Matt Chapman's Finite State Machine animator.

This is a Java Applet that allows you to draw FSMs in a window and experiment with them. - There is no need for a text book for this course, but those who are interested in more reading can see the following books: Computation: "An introduction to formal languages and automata" by Peter Linz. Logic: "The essence of Logic", John Kelly, 1997. if you still want to read more on logic: "Logic for computer science", Steve Reeves, 1990.

Informatics Forum, 10 Crichton Street, Edinburgh, EH8 9AB, Scotland, UK
Tel: +44 131 651 5661, Fax: +44 131 651 1426, E-mail: school-office@inf.ed.ac.uk Please contact our webadmin with any comments or corrections. Logging and Cookies Unless explicitly stated otherwise, all material is copyright © The University of Edinburgh |