Question on decidability w.r.t. tag systems

Question

I've read that it is known that tag systems in TS(2,2), that is, with two symbols and deletion number $2$, are decidable.

I suppose I'm asking for clarification on what that means in this context. I assume it means that at the very least, for any given system in that class, one can effectively calculate whether or not it eventually halts.

But what about more specific questions? In particular, I believe the simplest non-trivial system in TS(2,2) is $$\{a \rightarrow aab, b\rightarrow a\}.$$

It is immediately clear that almost all starting values grow without bound, and beyond that, there are definite patterns you can make headway on. However, it is not at all clear to me that, say, there's any closed-form way to determine whether the $k$th symbol added will be an $a$ or a $b$, or what the parity is after some number of rounds, or anything like that. My understanding is that Rice's Theorem wouldn't apply since a decidable system can't be Turing complete, so that doesn't answer it. So we know that any result we want can only take finitely long to calculate, but that leaves my main question:

Is it possible for a computational system to be decidable, yet have computationally irreducible properties which have no shortcuts and thus require actually doing all the intervening computation to determine?

Answer 1

It looks like it specifically says it’s not decidable and is Turing complete.

Also, apparently the particular case for having an alphabet with just two letters is not an exception, unless I am misunderstanding something else.

Where did you read it was decidable?

Answer 2

To start with, let me answer your first question. Decidability - in any context - refers only to the "raw" notion of the existence of an algorithm determining membership (or value, or etc.) which always halts. There is no assumption of feasibility, or "closed-formness," or anything else.

---

As to your main question, this is a very reasonable thing to consider, but it turns out to be deceptively difficult. The remainder of this answer merely addresses this the issue of framing your main question correctly; I am not going to attempt to answer it.

The issue is that the very notion of

computationally irreducible properties which have no shortcuts and thus require actually doing all the intervening computation to determine

is not nearly as clear-cut as it may appear. Roughly speaking, it's very difficult to "look inside" a computational process in a meaningful way without further assumptions on the nature of that process, and in particular "nicely analyzable" computations will always form a very small subclass of general computations. This is of course a highly informal principle (appropriately enough), but it is nonetheless an important obstacle to eventually come to terms with.

The best we can do in my opinion is look at complexity-theoretic concerns. For example, we could ask whether given a particular tag system the question "What symbol is added at stage $k$?" is computable by a polynomial-time machine. Note, however, that this only pays attention to the "extensional" behavior of the relevant algorithms, so it should not be construed as a fully satisfying framework for addressing your informal question.