# People

 Lecturer: Michael Fourman `mfourman @ed.ac.uk`

# Aims and Objectives

The goal of this course is to introduce you to computational thinking — using computational models to describe and reason about systems, including systems that change through time.

We begin by introducing some mathematical tools that help us to talk clearly and unambiguously. We then use these tools to study finite-state systems and propositional logic. These provide examples of the logical ideas of syntax and semantics and the computational ideas of structure and behaviour.

We will use sets, properties, relations, and functions to think and talk about computational systems.

Talking is all well-and-good, but talking in English, or any other natural language, is notoriously ambiguous, and we are often imprecise. We introduce a logical notation to make precise and unambiguous statements about computational systems.

### Computation

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 are used as basic computational models across the whole of Informatics and at the same time are used successfully in many widely used applications and components.

In future courses you will study more-general models of computation.

### Logic

Various logics are used for specifying and reasoning about informatic systems. Statements about finite systems can be expressed in propositional logic. We introduce two procedures for reasoning in propositional logic, and show that these can be used to solve many combinatorial problems. This provides a basis for later study of more general logics used to specify and reason about Informatic systems.

## Syllabus

• Sets, properties, relations and functions, used to model situations.
• Making clear and unambigous statements about situations, using logic.
• Describing the computational behaviour of physical systems, using states.
• Finite-state systems: a basic model of computation; deterministic and non-deterministic automata; regular expressions; acceptors; structured design of finite state machines.
• Propositional logic: truth tables, satisfiability; natural deduction, resolution; soundness, completeness.

This course provides students with experience of theory in a practical context. It also introduces a variety of 'professional issues' including software IP, verification, correctness, best practice and liability.

# Learning Materials

There is no textbook corresponding to this course. Chapters 1-3 of Mathematical Methods in Linguistics, by Robert Wall, Alice Ter Meulen, and Barbara Hall Partee (which you can download freely) provide a good reference for the basic mathematical tools we will use.

## Lectures

Normally Thursdays 11:10-12:00 and Fridays 14:10-15:00.

### Exceptions

Sometimes we will swop slots with INF1-FP. These swops are shewn in bold.

Week Monday 14:10-15:00 George Square LT Tuesday 11:10-12:00 LTA DHT Thursday 11.10-12:00 LTA DHT Friday 14:10-15:00 LTA DHT
1 INF1-FP INF1-FP INF1-CL INF1-CL
2 INF1-CL INF1-CL INF1-CL INF1-CL
3 INF1-FP INF1-FP INF1-CL INF1-FP
4 INF1-FP INF1-FP INF1-FP INF1-FP
5 INF1-FP INF1-FP INF1-CL INF1-CL
6 INF1-FP INF1-FP INF1-CL INF1-CL
7 INF1-FP INF1-FP INF1-CL INF1-CL
8 INF1-FP INF1-FP INF1-CL INF1-CL
9 INF1-FP INF1-FP INF1-CL INF1-CL
10 INF1-CL INF1-CL INF1-CL INF1-CL
11 INF1-FP INF1-FP INF1-CL INF1-CL

# InfBase

InfBase is in room 7.03 of Appleton tower, and is staffed from 11am-3pm on Monday through Friday during the normal semester (Weeks 3-11) and during Revision weeks. See the detailed schedule for when tutors with specific expertise will be present.

The course TA, Dave Cochran will be available in InfBase 1400-1500 on Wednesdays.

# Tutorials and Assignments

Tutorials, assignments, and readings are essential components of this course.

Tutorials: These start in week 2 and take place each week until the end of semester, including week 11. If you are ill or otherwise unable to attend one week then if possible you attend another tutorial in the same week.

If you wish to move to a different tutorial group, please ask the ITO through their online contact form and explain your constraints. Or visit them in Appleton Tower (level 6).

Students are expected to prepare for each tutorial, which includes completing the tutorial exercises and the reading.

You must attempt the work before the tutorial and bring with you a copy of the work you have done. Tutorials are mandatory, and the only way to learn is to do the work before the tutorial, not at the tutorial. Students who have not done the work in advance will be sent away.

## Tutorials

### 2017

Week 1:
MML Sections 1.1-1.7.
Week 2:
MML Sections 2.1-2.3 (to check your understanding, try exercises 1 & 2 on page 36).
Week 3:
MML Sections 6.1-6.4 (to check your understanding, try exercises 1 to 8 on pp 128-31).
Week 6:
Here are some online resources that present resolution. None of these covers 2-SAT as a special case, so you will be able to use the arrow rule to solve some of their examples of resolution. Earlier chapters of these books review much of the Propositional Logic material we have covered (and more besides).
Week 7:
Read the first two sections, and the section on applications, of the Wikipedia article on Finite State machines Sections 1.1-1.7.
Week 8:
MML Chapter 17 on Finite Automata and Regular Languages, up to and including most of page 468, presents most of the material we will cover on these topics. (The main exception is Arden's rule, which we will cover on Friday this week.)
Week 9:
The Wikipedia article provides a useful summary of the NFA to DFA Powerset construction.
Week 10:
The Wikipedia article provides a useful summary of the Sequent Calculus. Beware that in the "Reduction trees" section of that article proof trees grow downwards, whereas we grow our trees upwards. This means that the rules are presented upside-down (from our perspective). Confusingly, the example derivations in the following section on the system LK use our convention.

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. We model states of such systems using sets, functions, and relations.

For example, a marine weather report describes the state of the weather by reporting a finite number of attributes. Visibility is Good, Moderate, Poor, or Very Poor; Sea State has eight values, ranging from Smooth to Phenomenal.

A mariner may decide never to go out is the visibility is too poor or the wind is too strong, or the sea is too rough. Propositional logic can be used to express such conditions.

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 common theme is the analysis of complex systems using compositional descriptions. Complex truth tables are built using a few boolean operations. Complex machines are composed using primitives for sequential composition, alternation, and repetition.

• A brief introduction of computation as a process, and computational models as 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, inference and truth. The relationship between a proof and the validity of an implication in terms of truth tables. Searching for satisfaction: algorithms for finding models for systems of propositional constraints.
• 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 the design, analysis and construction of complex systems.

## References

Much of the material we will cover will only be presented in lectures. Copies of the slides, annotated with brief notes, will be available. The slides may be modified and expanded to clarify questions raised during the lecture, so they will normally be re-published a few days after each lecture.

Mathematical Methods in Linguistics, by Robert Wall, Alice Ter Meulen, and Barbara Hall Partee, ISBN-10: 9027722455 ISBN-13: 978-9027722454 (Part 1 of which you can download freely) provide a good reference for the basic mathematical tools we will use. It also covers a lot of material that goes beyond this course, much of which will be useful to you in future.

The brief notes I provide should be supplemented with notes taken by you during the lecture. If you are unable to attend a lecture, you should try to go through the slides with someone who did. Don't be shy about asking someone to do this — explaining things to you will probably help them at least as much as it helps you.

The first 5 chapters of Genesereth, Computational Logic, 2012, provide a good summary of much of the basic technical material on propositional logic covered in this course.

Another reference 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 :-)

## Context

This course supplies foundational knowledge for Informatics courses taken in subsequent years of study. It runs alongside the Informatics 1 Functional Programming course, which provides complementary experience in programming.

# General Information & Other Resources

1. inf1.hgs.club
2. Past papers for all Informatics courses and modules, organised by year. Search through each year to find available Inf1 Computation and Logic past papers.
3. Wikipedia is a good source for many topics, such as,