Skip to main content
2 of 3
edited tags
Joel David Hamkins
  • 236.3k
  • 44
  • 777
  • 1.4k

Is there a well defined subset of the integers that cannot be defined as a property of a recursive process or Turing Machine?

Is there a well defined subset of the integers that cannot be defined as a property of a recursive process or Turing Machine?

I have long been intrigued by the observation that much of mathematics can be defined as properties of recursive processes or Turing Machines. One can construct the arithmetic hierarchy by all finite iterations of the question: does a TM have an infinite number of outputs such that an infinite subset of these outputs are Gödel numbers of TMs with an an infinite number of outputs? One can construct the hyperarithmetic hierarchy by iterating this question up to all recursive ordinals. One can go farther by asking does a TM which accepts an arbitrarily long sequence of integer inputs halt for every possible infinite sequence?

These are all questions that are in some sense logically determined by a recursively enumerable sequence of events: all the possible paths a TM can take with any possible finite sequence of inputs. Can one define a subset of the integers that cannot be defined in this way? Saying that a set is the even integers if the continuum hypothesis is true and the odd integers otherwise does not count since both alternatives are definable as properties of a TM. On the other hand giving a recursively enumerable sequence of statements whose truth values cannot be encoded as a property of recursive processes would count.

Of course the notion of property of a TM is indefinitely expandable. but it must be limited to a process that depends only on a recursively enumerable sequence of events.