School of Computing and Information Systems COMP30026 Models of Computation Tutorial Week 1
5–7 August 2020
Introduction to tutes
Welcome to the first Models of Computation tutorial for 2020. We hope you will enjoy the tutorials, and also that you will contribute to making them enjoyable for your class mates. We have the luxury of having 2-hour tutes and we want to make the most of them, even if we cannot have face-to-face collaboration. Your tutor will explain how they would like to run the tutes. We are keen to preserve as much of the interaction and collaboration as we can, from the on-campus tutes that we are used to. Your willingness to engage online is critical, of course, and in particular we expect you to be active in tutes and in smaller Zoom break-out rooms.
Plan for the first week
This week the lecture will introduce some themes that come up later in the subject. Then we will plunge into a non-trivial Haskell program. The aim is to show that Haskell is useful for certain tasks, in particular tasks that involve symbolic computation. At this point many language details will be a mystery to you, and that’s fine. I hope to convince you that, with Haskell, it is possible to build useful tools with little effort. In the next weeks, your job is to use the available Grok modules to learn basic Haskell. Grok is a good platform for that, certainly better than lectures. You should have been given Grok access by now. (If you are enrolling late, it may take us a day or two to get you access.)
The exercises
1. Introduce yourself to your classmates and tell them a bit about yourself. Your tutor may place
muumuu
you in Zoom break-out rooms before or after this exercise. You may also want to discuss any
logistic/technological problems that you have (or think you may have) and share experiences
from semester 1—how do we make tutorials work for all of us?
2. Visit Grok and work through Haskell Module 1, “Functions and Recursion”. If you are fast, you may even get started on Module 2 on lists. Support the other students in your group. (We don’t plan to use tutorial time on Grok from Week 2 onwards; this is just to make sure you get started.)
3. Consider an n by m grid. We want to find out how many different paths there are that one can travel along, starting from the bottom left and ending in the top right cell, given that one can only move up or right. Write a Haskell function
paths :: Integer -> Integer -> Integer
so that paths m n returns the number of such paths. (We use Integers as the numbers can get quite large.)
4. In Lecture 1 we play a word rewriting game. Here is an example of a similar kind of game, the so-called Post’s Correspondence Problem. We have a set of “dominoes” such as
一
b , a ,ca,abc ca ab a c
The dominoes use a small alphabet, say the letters a, b, and c. Each domino has a string written in the upper half, and one in the lower half. The given set of dominoes is always finite, but there is an unbounded supply of each domino, that is, we can use it many times.
non-empty strings across the top and the bottom (or alternatively, determine that no solution is possible). For example, the set given above has a solution, namely
a b ca a abc ab ca a ab c
(a) Canyoufindasolutionto baa , aaa ? aaa baa abaaa aa au abaaa
(b)Howabouta ,bc, c ,abc? cb ba aa c
(c) How about ab , bba , aba ? aba aa bab
c
The goal is to find a sequence of dominoes which, when laid side by side, spell out identical
5. What is the general algorithm that solves Post’s Correspondence Problem?
口口口
器
㗊㗊
Starting Point
Constrained
Undecidable Problem
BFS
DFS
器器
No
solve the problem
Algorithm
can be developed to
b
1 o00
Ci
c
从 11
Aninteresting Example
Only one Domino
Haskell
New
Solution No
fun
十
Logician programming Language
Functioned Purely Functional
Functions i
No Sideeffect
Othercomponents not 哌吡 addOne x as sendEmail X
Eg
No loops Use Recursion
Useful waysofthinking
Input
output
L Lazy evaluation Evaluatingwhenyoumadthevalue
y my Save time resource
Need to force it Like use
L
Function Input Output
Types
E.g square fin
Operators
Types
to pre
compute
Statically typed Lowchanceofruntime error
Can tell you all errors youmadefrom hurt Compile Gmat Confidences
Variables Types
String
Int IntegersBigger Floats Doubles Body Boolean
Char
Listof Chars
11Haskell n 2 1 1M a t h
nnn 11
Recursion
迎了221
烈
So its like
fni.orgI argN
square square
output Int Int
nnn
max Int s Int s Int
ab Ifhilasbea
max
I otherwise b
Sumofa listofintegers 1 了 5.7
FunctionCall
izgǜ It5 了十四51770
1357
Sum in圢 Int
4
0 Pattern Matching
Sum
Sum xs headxstsumlt.cilxs
1，13.5 ⻔ 9 hedxsinxsixixsjsumlx.DK Xtsumxs
3
5，7 3，5，7