Topics in computability, complexity, constructivity and provability

Case, JohnThe three content chapters of this doctoral dissertation involve each of the concepts Computability, Complexity, Constructivity & Provability from the title. One of these chapters is devoted to showing that un verifiable programs need not be obfuscated. An application casts some doubts on an interesting 1980 argument of Putnam's. It is also shown that there is an acceptable programming system, of course with infinitely many universal simulating programs, presented so that it has exactly one verifiable such universal program, and there is another acceptable system presented so that it has no verifiable universal programs. Another chapter was suggested by two functions in Rogers' book which are based on eventual, currently unknown patterns in the decimal expansion of ?. One of them is classically and not at all constructively provably computable, and there is no known algorithm for it. For the other it is unknown whether it is computable. A problem is that advances in relevant knowledge about these now unknown patterns in ? may destroy Rogers' examples. Presented in this chapter is a safer computable real to replace ? so that the associated first function retains its classically provable computability, but has un provability of the correctness of any particular program for it. For the second Rogers' function ? is replaced by a real with each bit linear-time computable in the length of its position, but with the associated second function provably un computable. The last chapter features some computability results which are shown to provably require non -constructivity, e.g., that the program equivalence problem for acceptable programming systems is not computably enumerable (c.e.). Characterized is how to divide this example problem into non-trivial cases of disjoint index sets, where showing each of these index sets to be non-c.e. has a kind of unformity not found for the full equivalence problem, and each set's being non-c.e. is of ostensibly lower degree of nonconstructivity. Lastly, some related results are presented for natural run-time bounded programming systems--with run time bounds all the way down to linear-time. This chapter suggests a Reverse Mathematics project to minimize non-constructivity here and elsewhere.University of Delaware, Department of Computer and Information SciencesPh.D