Kobe Colloquium on Logic, Statistics and Informatics

以下の要領でコロキウムを開催します。

Date: 2016/7/26 (Tue) 3.00pm - 4.30pm Place: Room 421

Speaker: Bakhadyr Khoussainov (Auckland/Kyoto)

Title: Algorithmically random infinite structures

Abstract: Over the last two decades a significant progress has been made in the study of algorithmic random infinite strings. The main concepts of algorithmic randomness on infinite strings are based on the natural measure on the Cantor space. In spite of much work, research on algorithmic randomness has excluded the investigation of randomness for infinite structures such as graph, trees, algebras. The reason is that it was unclear how one introduces a meaningful measures into these classes of structures that would be pivotal in defining algorithmic randomness. We provide a solution to this problem. We present an axiomatic approach that introduces measure, and hence algorithmic randomness into various classes of structures. We prove the existence of algorithmically random structures with various computability-theoretic properties. We show that any nontrivial variety of algebras has an effective measure 0. This, for instance, implies that no finitely presented algebra in a variety is algorithmically random. We also prove a counter-intuitive result that there are algorithmically random yet computable structures. This establishes a connection between algorithmic randomness and computable model theory.

交通：阪急六甲駅またはJR六甲道駅から神戸市バス36系統「鶴甲団地」 行きに乗車，「神大本部工学部前」停留所下車，徒歩すぐ． http://www.kobe-u.ac.jp/guid/access/rokko/rokkodai-dai2.html

連絡先：菊池誠　mkikuchi@kobe-u.ac.jp