[seqfan] Undecidable sequences?

[Antti Karttunen]

The author of the unedited sequence
http://www.research.att.com/~njas/sequences/A161681
asks, "Is there such a thing as a undecidable sequence?"

Here I assume, that by "undecidable" we mean a sequence (set)
of numbers, which is recursively enumerable, but not recursive.

"A decision problem A is called decidable or effectively solvable if A
is a recursive set.
A problem is called partially decidable, semidecidable, solvable, or
provable if A is
a recursively enumerable set. Partially decidable problems and any
other problems
that are not decidable are called undecidable."
From: http://en.wikipedia.org/wiki/Undecidable_problem

Then, certainly "an undecidable sequence" listed in
monotone order (like A161681) is a contradiction in terms.
(Because then the complement could also be recursively enumerated,
and thus the sequence would be recursive, i.e. decidable.)
In this case I think it would be better to explicitly include in the
definition the
arbitrary limit one used when searching the terms of the sequence,
or list the terms in different order that would scan x^3-y^2 in
antidiagonal (or similar) fashion, and output all primes encountered.
(Possibly with repetitions, or filtering out previously encountered
ones.)


However, if I recall my few math.log. courses correctly,
almost any sequence (that is, N -> Z function)
that is not monotone, not surjective, and does not diverge towards infinity,
and of which no specific formula can be found,
that is, of which it is generally impossible to predict
which integer values it gets and when,
COULD in principle be undecidable.

However, to actually PROVE that some sequence
is undecidable requires standard gimmicks with
Gödelization and diagonalization. Am I right?
(And in general, these proofs seem to say that "_in general_
this class of problems is undecidable", like e.g. in case of Hilbert's
tenth problem.)
See also: http://en.wikipedia.org/wiki/List_of_undecidable_problems

So, please correct me if I'm wrong.

Now, to actually construct more of these kind of sequences
in somewhat natural fashion. E.g., one could use Wolfram's
rule 110 ( http://en.wikipedia.org/wiki/Rule_110 )
and weave to the definition of the sequence the halting state
of the Universal Turing Machine embedded in the CA.
(Or the nearest equivalent, whatever it is.)
However, Cook's proof requires using an infinite (non-zero)
background pattern, so...


BTW, there are more non-computable sequences in OEIS,
related to Turing machines:
http://www.research.att.com/~njas/sequences/?q=noncomputable


Yours,

Antti Karttunen