5
$\begingroup$

The standard definition of computability, for a sequence $s\in\{0,1\}^\omega$, is that there is a Turing machine outputting $s[i]$ on input $i$.

I'm looking for strengthenings of this notion; for example, in the above definition it's not decidable whether there is a $1$ in $s$; or, given $i$, whether there is a $1$ in $s$ at position $\ge i$. I would be happy to be shown a "natural" definition of computability that makes these predicates computable.

To the above: if there were an algorithm that, from the Turing machine producing $s$, tells us whether $s$ contains a $1$ then I could do the following: from any Turing machine $M$, program a Turing machine outputting $s[i]=1$ if $M$ stops after $\le i$ steps. This sequence $s$ is obviously computable --- I said how to compute it --- but an algorithm determining if the sequence contains a $1$ would solve the Halting problem.

A search through the literature didn't show anything, so links and references are most welcome!

Improve this question
$\endgroup$
4
  • $\begingroup$ Can you say more about what you mean by "strengthening"? It's a very broad question. If we view $s$ as a subset of all strings on a finite alphabet, where $s[i] = 1$ if and only if the $i$th string is in the language, then all of formal languages are relevant, e.g. regular, context-free, etc. $\endgroup$
    – usul
    Commented Nov 28, 2017 at 1:10
  • $\begingroup$ Yes, you're right that my question is imprecise. I was hoping that there was a large class of Turing machines for which, at least, the above predicates are decidable -- something much larger than rational. @usul, we might write $i$ in unary, and view $s\subset\{0\}^*$, or in binary, and view $s\subset\{0,1\}^*$, the answers will definitely be different but both interest me! $\endgroup$
    – grok
    Commented Nov 28, 2017 at 8:38
  • $\begingroup$ when you say "it's not decidable whether there is a 1 in $s$", I'm not sure what you mean. If you have in mind that the input is $s$ (an arbitrary element of $\{0,1\}^\omega$), this is not a possible input for a Turing machine: you can input an integer or an equivalent datum, e.g. a finite sequence. When you say "whether there is a 1 in $s$ at position $\ge i$", again the input can't be $s$, but let's say that the input is $i$. Then you get the characteristic function of an initial segment of $\omega$, and this is obviously a computable function. $\endgroup$
    – YCor
    Commented Nov 28, 2017 at 12:46
  • $\begingroup$ @YCor The input to that decision problem is obviously the sequence $s$. We can view this in two ways: The Polish style, where the sequence is written out on the input tape, or the Russian style, where the sequence is given by the code of a Turing machine that would write it. For natural problems, it usually makes no difference regarding decidability of questions, and this applies here. $\endgroup$
    – Arno
    Commented Nov 28, 2017 at 16:32

2 Answers 2

Reset to default
1
$\begingroup$

What a computable sequence is essentially follows from what computability is, and from what a sequence is.

Let us first agree that a sequence over $\mathbf{X}$ is a function $s : \mathbb{N} \to \mathbf{X}$. Then asking that whether or not a sequence over $\{0,1\}$ is constant be decidable amounts to

  1. Solving the Halting problem for whatever notion of computability we work with (as explained in the question)
  2. Demanding that $\mathbb{N}$ is compact (in the sense of synthetic topology)

This tells us that any notion of computability with this property is extremely weird, and probably should not be considered a notion of computability at all.

Of course, we could use a mixed view, where we use a restricted version of computability on the sequence, and a more powerful one to decide whether its constant. In that case, we just need that the second notion can decide the Halting problem for the first.

Alternatively, we could replace $\{0,1\}^\omega$ by something different, but similar. We can view this as $\mathcal{P}(\omega)$, but all standard notions of computability on this are weaker than $\{0,1\}^\omega$. Using Joseph Miller's $\Pi$-topology on $\{0,1\}^\omega$, we could get that whether sequence is constant becomes decidable. Unfortunately, there are no computable points in the $\Pi$-topology at all.

We could brute-force it, say by tagging any $p \in \{0,1\}^\omega$ by the cardinality of $|\{n \in \mathbb{N} \mid p(n) = 1\}|$, but I fail to see how this would be interesting.

Improve this answer
$\endgroup$
7
$\begingroup$

You can look at automatic structures, replacing Turing machines by finite automata. In that setting, the whole first order theory is decidable (in particular you can add existential quantifiers like you describe), by a Theorem of Hodgson.

Hodgson, Bernard R., On direct products of automaton decidable theories, Theor. Comput. Sci. 19, 331-335 (1982). ZBL0493.03002.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Thanks! (see my comment above) It also seems to depend heavily on the way in which we encode the index $i$. I see now that there's the notion of k-automatic sequence (en.wikipedia.org/wiki/Automatic_sequence), is this the same as what you have in mind? $\endgroup$
    – grok
    Commented Nov 28, 2017 at 8:43
  • $\begingroup$ Yes, I guess I mean 2-automatic $\endgroup$
    – Bjørn Kjos-Hanssen
    Commented Nov 28, 2017 at 21:34

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .