simon@psuvax.UUCP (Janos Simon) (11/01/83)
About halting: it is unclear what is meant precisely by "can a program of length n decide whether programs of length <= n will halt". First, the input to the smaller programs is not specified in the question. Assuming that it is a unique input for each program, known a priori (for example, the index of the program), then the answer is obviously YES for the following restriction: the deciding program has size 2**n and decides on smaller programs (there are a few constants that are neglected too). There are less than 2*2**n programs of length <=n. For each represent halting on the specific input the test is to apply to by 1, looping by 0. The resulting string is essentially the program needed - it clearly exists. Getting hold of it is another matter - it is also obvious that this cannot be done in a uniform manner for every n because of the halting problem. At the cost of more sophisticated coding, and tremendous expenditure of time, a similar construction can be made to work for programs of length O(n). If the input is not fixed, the question is obviously hopeless - there are very small universal programs. As a practical matter it is not the halting proble that is relevant, but its subrecursive analogues. janos simon