Mathematical Sciences: Some Recursion Theoretic Problems

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

DMS-96-22290 Harrington, U. Cal-Berkeley This project studies the recursively enumerable (re) sets of integers, in a way which is independent of their enumeration and independent of how integers are viewed as coding information. It is the study of re sets purely in relation to each other. The main ingredients of this study are: automorphisms of the collection of re sets - the symmetries that exist among re sets; and invariant sets - the walls that prevent symmetries. These two ingredients naturally go hand-in-hand. The main method used in this field is called `priority arguments'. This is a technique for performing computable constructions that ensure appropriate non-computable properties. A current guiding problem is: if an invariant set has non-trivial minimum information content then each of its members must have maximum information content. It is known that settling this would involve an extension of current automorphism techniques. A set is "re" (recursively enumerable) if it can be computably listed. For example, the set of all possible theorems of mathematics (deduced from the usual axioms) is re. This project studies the re sets themselves. Penrose, in his book The Emperor's New Mind, suggests an analogy between computing and consciousness. This projects seeks possibilities in the more strained analogy between re sets (independent of their enumeration) and the timeless aspects of consciousness. There are existing results which can be seen as indicative of this direction. The main method used in this field is called "priority arguments". This is a method whereby a common purpose can be achieved by establishing an extensive field of "world views", all working towards the common goal in their own separate ways, most of which are conflicting. One interesting feature of the method is that all reasonable world views must be allowed, including those that deny the common purpose (those world views do their jobs by working towards their own ne gations). Success in this project would strengthen the potentially profound implications of the analogy linking consciousness with a priority argument -like universe.