News
-
26 april Blackboard environment for the course available
Lecturer
- Clemens Grabmayer (mailto: clemens at phil dot uu dot nl)
Course timetable
-
course meetings
- Monday 11.00 - 12.45 , Ruppert building, room 136 (first meeting 26-04-2010);
- Wednesday 11.00 - 12.45
,
Ruppert building,
room 136.
- courses timetable CAI master, periode 4 2009-2010
Course material
- slides lectures
- original literature, and web-ressources
- (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, sigma-calculus
- speculative: hypercomputation
- emergent models: quantum computing, bio-computing
- Church-Turing Thesis on effective computability
- use of models of computation in AI-disciplines
More details
- for participants are now available 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. The aim is that feedback received can help everyone in writing the final version of the paper. Efforts displayed at giving feedback for others will be included, for a small part, in the final grade.