CA course syllabus

 

• 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