zpravodaj ČSKI
aktuální číslo
přednáška
archiv
  - 2019
  - 2018
  - 2017
  - 2016
  - 2015
  - 2014
  - 2013
  - 2012
  - 2011
  - 2010
  - 2009
  - 2008
  - 2007
  - 2006
  - 2005
  - 2004
  - 2003
  - 2002
  - 2001
  - 2000
  - 1999
  - 1998
  - 1997
  - 1996
  - 1995
  - 1994
 
 
zpravodaj ČSKI - únor 2013 [ pdf ]
[ zaslat oznámení o přednášce ]
leden|únor|březen|duben|květen|červen|říjen|listopad|prosinec


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.