Home > News > David Gajser: Some (un)decidable languages

David Gajser: Some (un)decidable languages

Date: 2. 4. 2012
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))?