David Gajser: Some (un)decidable languages
Source: Graph theory and algorithms seminar
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))?