News
| April 22, 2013 | This webpage online |
| April 29 | First course meeting |
Lecturer
- Vincent van Oostrom (mailto: Vincent.vanOostrom at phil dot uu dot nl)
- Clemens Grabmayer (mailto: Clemens.Grabmayer at phil dot uu dot nl)
Course timetable
-
Check the time of the course meetings in Osiris:
Go to Osiris course search page
and enter the course code WBMV09005 or the course name `models of computation'.
-
Course meetings
- Monday 09.00 - 10.45 , Drift 25, room 0.05, first meeting 29-04-2012.
- Wednesday 11.00 - 12.45
,
Drift 25, room 0.01.
Course material
- slides lectures
- original literature, and web-resources
- (as a gentle introduction) the book:
Maribel Fernández: Models of Computation (An Introduction to Computability Theory), Springer, 2009.
Aims
- The aim of this course is to get acquainted with some of the most frequently used models of computation in computability theory and logic, and in the disciplines of AI. Classical and less well-known models will be studied. Relationships between these models will be established via simulations. The Church-Turing Thesis about effective calculability will be explained, evidence for it, and possible limitations of this statement, will be discussed. Some non-classical models of computation and their reach will be treated. Furthermore, applications in AI-disciplines will be considered.
Topics
- models of computation:
- classical models: Turing machines, Post machines, λ-calculus, generalized recursive functions (Gödel-Herbrand computability), Combinatory Logic, μ-recursive functions, register machines, Post canonical systems (tag systems), Markov algorithms
- less well known: Fractran (Conway)
- more modern: neural networks, cellular automata, term rewrite systems, interaction nets, process algebra, ς-calculus
- speculative: hypercomputation
- emergent models: quantum computing, bio-computing, reversible computing
- Church-Turing Thesis on effective computability
- use of models of computation in AI-disciplines
- comparisons of, and simulations between, different models of computations
Guest lectures
to be announcedMore details
- for participants will become available in the evening of Wednesday 24-04-2013 via a Blackboard-environment for the course at http://uu.blackboard.com/
Assessment
- paper / presentation / feedback* for others
*: Apart from giving a presentation about a machine model, or about a connected topic, and from writing a paper about that (the assessment points mentioned in the course description in Osiris), it will be asked to give feedback on preliminary versions of other participants.