発表者：並川淳

日時：10/11 15:00
場所：知識3棟8階

内容：次の論文を紹介します.

・Frederic Geurts, "Hierarchy of Discrete-Time Dynamical Systems, a Survey",
Bulletin of the European Association for Theoretical Computer Science, 57, 
230-251, 1995.

アブストラクト：

この論文はTMやセルオートマトンを離散力学系と見なしたときの記述能力の差について
述べたものである.
ここでは, 最初にTMやセルオートマトンなどを統一的に記述できる系として
generalized DTDS を定義し, 次にこれらの記述能力を比較する方法について議論する.
次に, TMやセルオートマトン, [0,1]上の連続力学系などを比較する.
その結果, 記述能力の大きい順から「実数空間上の連続な離散力学系 ≧ CA > TM」
という結果が得られる.