The nature of uncomputability

[djr...@bath.ac.uk]

I have read a bit about second order arithmetic and increasing
complexity, and how some sets of numbers are uncomputable (e.g. the
set of numbers corresponding to Chaitin's constant). Does the notion
of an uncomputable set extend any higher, i.e. to sets of sets of
numbers (third order arithmetic)?

[djr...@bath.ac.uk]

Actually, I guess I mean "complexity" rather than "uncomputability".
No computer program can rattle off one by one the elements of an
uncountable set!

[Also, "number" means "natural number", naturally.]

[Baudouin Le Charlier]

Computable means: there is an algorithm (a Turing machine) to compute
it. For instance, le real number pi is computable because there is an
algorithm that 'lists' all its digits. It will never stops but we can
go on until we reach any desired precision. Most reals are not
computable in this sense however since the set of Turing machines is
countable.

Baudouin

[ju...@diegidio.name]

You might be interested in this article, which I have googled anyway:

http://plato.stanford.edu/entries/logic-higher-order/#4

"We have seen that, although the set V¹ of valid formulas of first-
order logic is computably enumerable, the corresponding set V² for
second-order logic (with the standard semantics) is vastly more
complex. This phenomenon does not continue into the higher orders."

-LV