Information Technology Seminar I: Schedule

Understanding Computation

Aoyama Gakuin University, Summer 2018, Martin J. Dürst (last updated 2018-07-18)

(links to presentations and minutes are only accessible with a password)

Chapter and page numbers refer to Understanding Computation - From Simple Machines to Impossible Programs, Tom Stuart, O'Reilly, 2013.

Code for this book is available at (use Download ZIP if you don't want to install git). To execute, move to the directory where the code is and start irb with irb --simple-prompt. Once in irb, use require 'absolute_program_name' or require_relative 'relative_program_name'.

April 11
Introduction: Martin J. Dürst
Homework for April 18: Install Ruby (install the latest versions of Ruby 2.5 (or Ruby 2.4) from RubyInstaller (including Devkit), or make sure that your cygwin installation includes a recent Ruby version)
For a gentle introduction to Ruby, please also see Programming Basics II (2011)
April 18 (Martin J. Dürst)
Introduction to Ruby (pp. 1-14 + Learning Rails, Logic and Conditionals, pp. 340-347)
April 25 (minutes: 久田)
a) Programs and Machines (pp. 15-32): 小野
b) Statements (pp. 33-48): 高橋
May 2 (minutes: 小野)
c) Denotational Semantics (pp. 49-62): 原田
d) The Simplest Computers (pp. 63-79): 高田
May 9 (minutes: 高橋)
e) Regular Expressions (pp. 79-94): 立川
f) Equivalence and Minimization (pp. 94-103): Schalkwijk
May 16 (minutes: 原田)
g) Just Add Power (pp. 105-118): 東
h) Nondeterministic Pushdown Automata (pp. 118-134): 澤浦
May 23 (minutes: 高田)
i) The Ultimate Machine (pp. 135-147): 伊藤
j) Nondeterministic Turing Machines (pp. 147-158): 稲葉
May 30 (minutes: 立川)
k) Computation and Computability (pp. 159-174): 前川
l) Numeric Operations (pp. 174-192): 久田
June 6 (minutes: 前川)
A) Advanced Programming Techniques (pp. 192-206): 原田
B) Universality is Everywhere (pp. 207-224): 東
June 13 (minutes: 伊藤)
C) Iota, Tag Systems (pp. 224-235): Schalkwijk
D) Cyclic Tag Systems (pp. 235-251): 小野
June 20 (minutes: Schalkwijk)
E) Impossible Programs (pp. 253-269): 立川
F) Decidability (pp. 269-284): 高橋
June 27 (minutes: 東)
G) Programming in Toyland (pp. 285-296): 稲葉
H) Implementation (pp. 296-308): 澤浦
July 4 (minutes: 澤浦)
I) Ruby Gems: Main parts of Rubygems Guides (presentation): 久田
J) Bundler: Various pages from, How does Bundler bundle? (presentation): 高田
July 11 (minutes: 稲葉)
K) SVuGy - Exploring the Space between Procedural and Declarative Graphics (presentation): 前川
L) Ruby on Rails: The Rails Doctrine (presentation): 伊藤
July 18: Research at the Software Lab (reports by B4/M1/M2 students and interns):
(July 25: makeup classes)
(July 26 to August 2: Term final exams)