Authors:

• Werner Gitschthaler e-mail: wgitscht @ cosy . sbg . ac . at
• Harald Roeck e-mail: hroeck @ cosy . sbg . ac . at
• Rudolf Dittrich e-mail: rdittrich @ cosy . sbg . ac . at

Project description

Within the course Theroy of Computational Systems we had to define a mini theory of computation or systems with some interesting properties. These properties have to be proved and finally written down in a project report.

Abstract

We report on a new computational model namely the Deadline Turing Machine DTM. The DTM uses a deadline within words of a given language can be recognized and decided. If a word cannot be decided within the deadline it is rejected by the DTM. This property implies that opposed to a Turing Machine it always halt. Moreover, a DTM can easily be mapped on a Turing Machine and is equal to it if and only if the deadline is infinite. Finally, we also show that there exists a Universal Deadline Turing Machine which can be built of a TM with two tapes and two separate heads.

The paper: dtm.pdf.