CA course syllabus

 

Spring semester 2024
Cellular Automata

 

Lectures (28 times 2 hours)

  • 10:15-12:00 Wednesdays in room M1 (Quantum, 2nd floor)
  • 10:15-12:00 Fridays in room M4 (Quantum, 3rd floor)

Homework sessions (13 times 2 hours)

  • 10:15-12:00 Mondays in room M1 (Quantum, 2nd floor)

Course Web Page: http://users.utu.fi/jkari/ca2024

Instructor: Jarkko Kari <jkari@utu.fi>; office: Quantum 365, 3rd floor

Prerequisites:

  • No formal prerequisites. Tilings&Patterns, Topology, Automata theory are recommended.

Textbook:

  • No textbook. Lecture notes will be posted on the course web page.

About homework:

  • To pass the course, at least 25% of the homework problems must be completed. The more problems you solve, the more credit towards the final grade you get: You get demo class
      • A, if you complete 70%-100%,
      • B, if you complete 45%-70%,
      • C, if you complete 25%-45%

      of the given problems.

Midterms

  • Two midterm exams: Dates TBA.
  • Not mandatory. The class requirements can also be satisfied by taking a single final exam.
  • Both midterms (3 hours) consist of 4 problems, each of which has maximum score of 4 point.
  • A minimum of 5 points is required in both midterms.
  • Homework activity (demo class A, B or C) and the combined score of the two midterms determine the final grade according to the following table:

Final Grade

Demo class

A

B

C

1

13-14

14-15

15-16

2

15-18

16-19

17-20

3

19-22

20-23

21-24

4

23-27

24-28

25-28

5

28-32

29-32

29-32

Final exam:

  • An alternative way to pass the class. One can take the exam more than once (even if one has passed the course) to improve the final grade.
  • Dates TBA
  • Anyone with democlass at least C has qualified to take the exam within one year.
  • Exams (4 hours) consist of 5 problems, each of which has maximum score of 8 points.
  • Homework activity (demo class A, B or C) and the score of the final exam determine the final grade according to the following table:

Final Grade

Demo class

A

B

C

1

17-18

18-19

19-21

2

19-23

20-24

22-26

3

24-29

25-30

27-31

4

30-34

31-35

32-36

5

35-40

36-40

37-40

Tentative course outline

  • Basic definitions of cellular automata and symbolic dynamics
  • Injectivity, surjectivity, reversibility
  • Balance theorem, Garden-of-Eden theorem
  • de Bruijn representations, algorithms for 1D CA

1st midterm

  • Undecidability in CA
  • Computational universality in CA
  • Reversible CA
  • Conservation laws
  • Hedlund’s theorem
  • Dynamical properties of CA, limit sets

2nd midterm