$\DeclareMathOperator\Comp{\mathit{Comp}} \DeclareMathOperator\succ{\mathit{succ}}$Let $(\Phi_e)_{e\in\omega}$ be your favorite enumeration of Turing machines. For $e,n\in\omega$ there is a structure $\Comp(e,n)$ naturally associated to the run of $\Phi_e$ on input $n$. Intuitively, $\Comp(e,n)$ is an $\omega\times\omega$-array whose $(a,b)$th entry codes the state of the computation $\Phi_e(n)$ at stage $n$.

More formally:

  • The domain of $\Comp(e,n)$ is $\omega^2$, with "$(a,b)$" representing cell $b$ at time $a$.

  • The language of $\Comp(e,n)$ consists of: unary function symbols $\succ_t$ and $\succ_s$ (for moving in time and space respectively; a unary relation symbol $S_q$ for each of the finitely many states $q$; a unary relation symbol $A_x$ for each of the finitely many alphabet symbols $x$; and a unary symbol $H$ for the tape head.

  • We set $\succ_t((a,b))=(a+1,b)$, $\succ_s((a,b))=(a,b+1)$.

  • We set $S_q((a,b))$ iff at stage $a$ the computation is in state $q$.

  • We set $A_x((a,b))$ iff at stage $a$ the $b$th cell on the tape has symbol $x$.

  • We set $H((a,b))$ iff at stage $a$ the head of the Turing machine is at cell $a$.

  • We use the convention that if the computation halts, we just copy the final configuration forever.

(Note that the actual program, i.e. the transition function, is not coded into the structure; $\Comp(e,n)$ only tells us what happens, not why it happens. That said, this isn't an essential point, and any reasonable tweak will result in an appropriately-equivalent structure.)

My question is about the logical complexity of these structures. Trivially, if $\Phi_e(n)\downarrow$ then $\Comp(e,n)$ is decidable. Broadly, I'm interested in what general tools we might use to prove decidability of $\Comp(e,n)$ when $\Phi_e(n)\uparrow$.

More specifically, say that $\Phi_e$ is run-decidable if $\Comp(e,n)$ is decidable for each $n$. Note that we consider each run of $\Phi_e$ individually here, and do not even demand that $\Comp(e,n)$ be decidable uniformly in $n$. My question is:

Is every c.e. set the domain of some run-decidable machine (at least up to Turing degree)?

(I'm happy to shift attention to the analogue of $\Comp(e,n)$ for other models of computation if that would help.)

  • $\begingroup$ What does it mean for a structure to be decidable, that the FO theory is? $\endgroup$ – Ville Salo Apr 29 '20 at 18:03
  • $\begingroup$ @VilleSalo Exactly. $\endgroup$ – Noah Schweber Apr 29 '20 at 18:04
  • $\begingroup$ People study Turing machines as dynamical systems, and one thing they do is think about how complex the spacetime diagrams (these are your structures) are. That might or might not be relevant, I certainly don't see the answer though. $\endgroup$ – Ville Salo Apr 29 '20 at 18:07
  • $\begingroup$ @VilleSalo Yes, I took a glance at the subshift literature especially in this context, but I didn't find an answer there (I'm not very familiar with it, though). $\endgroup$ – Noah Schweber Apr 29 '20 at 18:08
  • 1
    $\begingroup$ @LSpice I like \mathit - I didn't know that was an option! I'll definitely use it in the future. (For my eyes, the mathoperator mode blurs into normal text. You're absolutely right about the kerning issue.) I've also thrown in extra parentheses to address the arity issue. $\endgroup$ – Noah Schweber Apr 29 '20 at 20:08

I was just about to leave for my biquarantinely jog when you asked this nice question, sorry about the quick comments which if anything have lead you to a wild goose hunt. I think the answer is yes, with a much easier trick than the ones I suggested.

First of all, my understanding is that with just successors and first-order logic, all you can do is count finite patterns. If you can do more than that, then the following may not be enough.

The idea is to simulate counter machines with our Turing machine: the machine reads the input, and verifies that it is of the form $ 0^n 12\#0^\omega$ (I assume the input is finite and you have an end-marker $\#$, and you are promised the rest is $0$s). If it's not, just halt. Otherwise, erase the end-marker, go back to the origin of the tape, and start simulating a universal two-counter machine by zig-zagging between the origin and the $2$, moving $1$ and $2$ (keeping them in this order).

The invariant linking the Turing machine run and the counter machine is that when the head returns to the origin for the $m$th time, the tape looks like $q 0^k 1 0^\ell 2 0^\omega$ where $(q,k,\ell)$ is the state of the counter machine after $m$ steps.

Now, assuming I understand what decidability of first-order logic amounts to with your definitions, all you have to be able to decide about the spacetime diagram is counting, i.e. it is sufficient, given a pattern $P$ and a number $k \in \mathbb{N}$, to be able to decide whether $P$ appears at least $k$ times in the spacetime diagram.

Now, the point is that any particular diagram has a finite amount of this type of counting information, because all you have to remember is in which states the head traverses from $1$ to $2$ (or $2$ to $1$, or origin to $1$, or $1$ to origin) infinitely many times, and whether $1$ and $2$ meet infinitely many times and in which states.

Two-counter machines can accept the set $\{(2^n,0) \;|\; n \in S\}$ for any $\Sigma^0_1$ set $S$, so also the set of $0^n12$ on which this machines halts is undecidable if we pick a suitable counter machine to simulate. (Note that on other inputs the machine halts and certainly the spacetime diagram is decidable since it's Presburger.)

edit 5th May 2020

Here's some additional observations and details. I have fixed the argument above a bit as well, as I realized there was a small mistake in what I was counting (I decided exact counts of occurrences of patterns, but we want to decide lower bounds on number of occurrences instead).

Preprocessing: any $\Sigma^0_1$ set can be accepted by a run-computable machine

Obviously any decidable preprocessing can be done to the input, as this only adds finitely many new initial rows of the grid for each input, which does not affect decidability by an easy argument. So we can make our Turing machine turn an arbitrary input $w \in \{0,1,2\}^* \# 0^\omega$ into the form $0^{2^{n(w)}}120^\omega$ where $n : \{0,1,2\}^* \to \mathbb{N}$ is any computable injection (the alphabet doesn't matter either, but I used a ternary one plus marker in the original construction so I'll keep that).

How does the two-counter universality work, again?

Let me recall the outline of the classical argument that we can compute absolutely anything about $n$ if the input is given as $0^{2^n} 12$ and we can only simulate a two-counter machine as I described, just because I can't bother finding a reference.

The way two-counter counter machine universality is usually proved is in two steps, first we simulate Turing machines with three counters, then three with two. So first assuming the Church-Turing thesis, we can compute anything using a Turing machine. A Turing machine's configurations are of the form $u q v$ where $u$ and $v$ are finite words, say over alphabet $\{0,1\}$. We simply replace them with the numbers they present in binary, and we can simulate a Turing machine using just two counters, as long as we can do the following operations to the counters:

  1. Check the parity of a counter (to read a bit).

  2. Divide/multiply a counter by two (to move the head).

With a basic counter machine, we assume we are only allowed to shift the counter values by one and check for zero. So we cannot do the above. Instead, we add a third counter, and now we can check parity of counter number $1$ by moving its contents to counter number $3$ two values at a time, and at the end we see the parity, and move everything back. Multiplying and dividing works the same. It follows that with three counters we can compute anything with two inputs given in the first two counters, assuming the third counter initially contains $0$.

Now to simulate $k$ counters with two, take $k$ distinct primes $p_1, ..., p_k$, and the correspondence is that $k$ counters containing values $(v_1, ..., v_k)$ is replaced by having the first counter contain $p_1^{v_1} p_2^{v_2} \cdots p_k^{v_k}$ and the second contain $0$. You can increment the simulated counter $i$ by dividing the first counter value by $p_i$, and similarly we can divide and check its parity (checking parity means checking whether $p_i$ divides the counter value an odd or an even number of times). Picking $p_1 = 2$, we see that if the input is $2^n$ we can think of the first simulated counter as containing $n$, and the others (however many auxiliary counters we want to use) contain $0$.

What's a pattern and what's "appearing"?

I should maybe explain what I mean by patterns appearing, since this is different terminology than what the asker used. I think of the structure as being an element $x \in A^{\omega^2}$ where $A$ is a finite alphabet containing the information about whether the head is in the current position and what the tape symbol is. I call this the spacetime diagram. A pattern is an element of $A^D$ for finite $D \subset \omega^2$ and appears means $\sigma^{v}(x)_D = P$ for some $v \in \omega^2$, where $\sigma^v$ is the shift, defined by $\sigma^v(x)_u = x_{u+v}$. I say $P$ then appears at $v$ and we say $P$ appears $k$ times if it appears at $v_1, v_2, ..., v_k$ for distinct vectors $v_i \in \omega^2$, and does not appear at any $v \notin \{v_1,v_2,...,v_k\}$.

What's the finite information we need to ask from an oracle, exactly?

Some more details (though still just a sketch) on why we only need a finite amount of information about the spacetime diagram to be able to decide every FO query, for now believing it amounts to counting how many times a given pattern appears. For this it is helpful (though not strictly necessary) to slightly modify the two-counter machine we simulate without changing its halting on any input: Let's assume the two-counter machine behaves as described above, and simulates a $k$-counter machine as described. Let $p$ be a prime it does not yet use to simulate the counters, and have it multiply the first counter value by $p$ between every two steps. Then we have that given $n$ we can compute $m$ such that after $m$ steps at least one of the two simulated counters will always have value at least $m$.

Now, having done that preprocessing, let me explain how you can decide whether a pattern $P \in A^D$ appears in the spacetime diagram $x$ at least $n$ times (and we'll see what information I need to query), assuming the computation never halts (if it halts, it's a Presburger/semilinear spacetime diagram anyway, so trivially FO queries would be decidable).

First, as discussed above, changing finitely many initial rows of $x$ does not change anything (there is a decidable procedure that modifies an FO query to take this into account). So we may assume that in the spacetime diagram $x$, at least one counter value is always larger than the maximal distance between any two elements of $D$. Now, observe that the only sort of thing $P$ may contain is

  1. in $P$ we see just static stuff, no head and at most one counter values. Anything like this will appear infinitely many times (assuming the machine does not halt) so we actually need no information to answer such a query. (Anything where the contents of $P$ does not change from row to row that is, otherwise obviously it does not appear in any spacetime diagram since the configuration is only modified when the machine head moves on it.)

  2. in $P$ we see a lone Turing machine head traveling on a bunch of zeros. This type of queries are easy, we just need to know in which state cycles the head moves over large zero areas infinitely many times.

  3. in $P$ we see shows a Turing machine head hitting one of the counters (and possibly moving it). There are a few different cases here, let's concentrate on the case where the head of the Turing machine hits the $1$-counter (= leftmost of the two) in some state $q$, and we see $m$ many $0$s to the left of that counter in our picture. Now, we need to be a bit careful: the $m$ many zeroes to the left mean that the counter value has to be at least $m$ at this point. Obviously we cannot remember, for each distinct $m$, whether the head hits the $1$ counter with such particular $m$. So a crucial observation is that if we hit the counter at some point so that the counter value is at least $m$, then our simulation is in fact currently in a cycle where it is continually decreasing or increasing the first counter value and decreasing the other. So actually either before or after this step, we see the exact same pattern after a constant number of steps, with a smaller $m$. This is why all we need to actually know is the pictures we see for small $m$. (The preprocessing where we keep multiplying by $p$ removes the cases where both counters contain a small value.)

Why is FO just pattern counting?

First-order definability (for this particular structure!) is the same as threshold-counting, see e.g. https://www.sciencedirect.com/science/article/pii/S0890540196900188 for such a result. (I have not actually read this paper, and it's probably not the optimal reference; it's about finite pictures rather than infinite ones; but anyway same idea.)

What that means is, if you have an FO formula $\phi$, then you can effectively find a finite list $P_1, P_2,... , P_k$ of patterns, and a subset $S \subset \omega^k$ which for some $n_0$ satisfies $t \in S \iff t + e_i \in S$ whenever $t_i > n_0$, where $e_i = (0,0,...,1,0,0,...,0)$ is the $i$th standard generator of $\omega^k$ as a monoid; such that $\phi$ is true for $x \in A^{\omega^2}$ if and only if $(t_1, ..., t_k) \in S$, where $t_i$ is defined by $$ t_i = |\{\mbox{number of times } P_i \mbox{ appears at in } x\}|. $$ And vice versa you can go from $P_1, P_2 ,... ,P_k$ and such $S$ to an FO formula.

If we just want to decide an FO formula, you only need to be able to check for a single pattern $P$ and $n \in \mathbb{N}$ whether $P$ appears at least $n$ times: given a formula $\phi$, turn it into $P_1, P_2 ,..., P_k$ and $S \in \omega^k$ as described above, and use that decidability result finitely many times as a subroutine to check whether $t \in S$.

Independence of accepted language and run-decidability

As mentioned, any $\Sigma^0_1$ set can be accepted by a run-decidable machine. But of course any $\Sigma^0_1$ set is also accepted by a strongly run-undecidable machine, namely one whose spacetime diagram is undecidable for all non-halting inputs: simply make the machine, while doing its main computation, also simulate the computation for some $\Sigma^0_1$-complete language $L \subset \omega$, and write $10^n1q$ somewhere in the spacetime diagram for all $n \in L$, $q$ marking the position of the head when it's written. (This cannot appear in the original input so if we take some care it does not interfere with whatever the actual language is we want to accept.)

Can we make an even more run-decidable Turing machine?

One may ask if we can do more than decidability of FO logic, say monadic second-order logic. Good question, I don't know the answer!

  • 1
    $\begingroup$ Biquarantinely = this will be your second one? $\endgroup$ – LSpice Apr 29 '20 at 19:33
  • 2
    $\begingroup$ Or my first one, and I'm hopeful. $\endgroup$ – Ville Salo Apr 29 '20 at 19:34
  • $\begingroup$ I realized that there's a lot of tricks here that you may need to have a computer science degree to know. I tried writing some of it out in the edit just now, but perhaps it just looks more incomplete now since there's now more places for missing details :) Best I can do for now, I'm happy to try to explain some of the steps if something is unclear. $\endgroup$ – Ville Salo May 5 '20 at 13:36
  • $\begingroup$ Oh, I didn't notice that the original question asks about every c.e. set. Today's edit also clarifies that this follows from the original construction. (Not just up to degree, but exactly.) $\endgroup$ – Ville Salo May 5 '20 at 13:39
  • $\begingroup$ It will take me a bit of time to accept this answer, but thanks (and it's certainly worth the bounty!). $\endgroup$ – Noah Schweber May 8 '20 at 19:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.