# David Gajser: Some (un)decidable languages

Date: 2. 4. 2012

Source: Graph theory and algorithms seminar

Source: Graph theory and algorithms seminar

Četrtek 5. 4. 2012 ob 12:15 v predavalnici 3.05 na Jadranski 21

**Abstract:** In this seminar, we will first review some basic results about decidability of some languages. Then we will focus on a special case: For a fixed function T(n), does there exist an algorithm, which solves:

Input: description of a Turing machine M

Question: Does M run in time <= T(n)?

Who would say, that the answer (about existence of an algorithm) is different when T(n)>=n log(n) and when T(n)=o(n log(n))?