[logic-ml] Kobe Colloquium: July 26, 2016, Bakhadyr Khoussainov

[Makoto Kikuchi]

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 at kobe-u.ac.jp