Mathematical Sciences: Recursive Model Theory

点击翻译按钮获取中文摘要

Knight is continuing her work in recursive model theory. Over the past two years, she has obtained several results on degrees of models realizing prescribed sets of bounded complexity types (finitary or infinitary). The problem of characterizing the degrees of isomorphic copies of a given model now seems approachable. Knight and Slaman have a characterization for models of finite Scott height. The characterization is unpleasantly complicated, and they hope to simplify it. The recent results use a powerful method of Harrington. In addition to using the method to obtain further results, Knight hopes to come to a better understanding of the method itself. Ash developed a related method and proved a theorem giving general conditions under which his method works. Ash and Knight have begun trying to compare the two methods. All of these investigations shed further light on the theoretical limits of computing power, a matter that becomes increasingly relevant and fascinating as the actual limits of computing power expand with each generation of new machines.