TÖL203F Algorithms, Logic and Complexity

Project

The project involves students picking one subject related to the course material and giving a 20 min. talk. The talks should be in Powerpoint (or similar) form and they will be placed on the course website afterwards.

The talks will be graded based on four elements: contents, organization, quality of slides, and presentation.

Below is a list of available topics. You can also suggest other topics, but they have to be related to the course material. Only one student can pick each subject - first come, first gets! You should have picked a topics before March 3rd.

Some of the topics have a reference linked to it, but if a link is missing then you should be able to get more information using Google. Also don't hesitate to seek out other references than then one provided.

• Quantum computation - survey of progress [Thomas Bressac]
• Turing completeness - explain it and its significance [Björn]
• How to build a Turing machine in SQL [Ingvi]
• Languages that are designed to be primitive recursive, like LOOP [Arinbjörn]
• Kolmogorov complexity - explain the concept and its usage
• The Ackermann function - describe the function and its computational properties [Jónas]
• Other models of computation, equivalent to the Turing machine, such as
  • Turmite [Hannes Pétur]
  • Game of life [Tom]
  • Peterson's worm [Jökull]
  • Wang's B-machine
  • or other interesting models
• An Oracle machine is a Turing machine with an oracle - explain and explore its possibilites [Magnus]
• You can also look for recent papers from theoretical computer science conferences: STOC og FOCS

The presentations will start on monday March 17th.