David Gajser: Some (un)decidable languages

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))?