datum: 27.2.2013 v 14:00
název: Nová hierarchie pro Turingovy stroje a cesta od hierarchií k branching programům
přednášející: Stanislav Žák (UI)
místo konání: UI, 2.patro, místnost č.318

souhrn: Krátce se seznámíme s jádrem konferenčního příspěvku Žák+Šíma "A Turing machine distance hierarchy" (LATA, duben 2013). Jedná se o novou míru složitosti výpočtů na Turingových strojích. Míra je půvabná (zachycuje dlouhé transfery informace na pásce Turingova stroje) a kromě toho souvislosti nalezené při prvním ohledání tématu kladou nové otázky. Poté učiníme dlouhou sérii neformálních poznámek, která zachytí historii jedné cesty od hierarchií k teorii branching programů a která se dotkne důležitých momentů jejího rozvoje až do dnešní doby (1978 - 2013). Zakončíme otázkou týkající se branching programů, která by snad mohla být výzvou pro kolegy pracující v matematické logice.