First a word on notation. Let an uppercase Latin letter except $S$ be a free variable. Let a lowercase Latin vowel be a variable bound a universal quantifier. Let a lowercase Latin consonant be a variable bound by a non-universal quantifier. Let $\text{FV}(\varphi)$ denote the free variables of $\varphi$ and let $\chi[M := \psi]$ be a capture avoiding substitution replacing $M$ with $\psi$ in $\chi$.
Robinson arithmetic replaces Peano arithmetic's axiom schema of induction with the following non-schematic axiom.
$$ Y = 0 \lor \exists x \mathop. Sx = Y $$
We can rephrase this as
$$ \forall a \mathop. \exists x \mathop. a=0 \lor Sx = a $$
I'm wondering what happens if we allow the full axiom schema of induction shown below, but constrain $\varphi$ to be an $\exists\forall$ sentence. I chose this constraint specifically to make the only zero has no predecessor claim inexpressible.
$$ (\varphi[X:=0] \land \forall a \mathop. \varphi[X:=a] \to \varphi[X:=Sa]) \to \varphi[X:= Sa]$$
This amounts to imposing the following constraints.
$$ \text{FV}(\varphi) \subset \{X\} $$
$$ \varphi \;\; \text{must be of the form} \;\; \exists x_1 \cdots x_n \mathop. \forall a_1 \cdots a_m \mathop. \psi \;\; \text{where $\psi$ is quantifier-free} $$
I'm pretty sure that this construction doesn't run afoul of this result because I'm not adding in all the true facts about the standard model of arithmetic. Unless I'm missing something, at least the fact that all non-zero numbers have a predecessor cannot be proven.
Post-script
I'm really not sure about what to do with parameters in $\varphi$, discussed here among other places. I'm assuming that I need to prohibit them but I'm not really sure.
Best Answer
This theory isn't decidable, since a subtheory of a finitely axiomatizable undecidable theory is never decidable. Specifically, your theory is a subtheory of (for example) the finitely axiomatizable theory $I\Sigma_2$. Let $\theta$ be a one-sentence axiomatization of $I\Sigma_2$, and $\varphi$ an arbitrary sentence in the language of arithmetic; then $\theta\rightarrow\varphi$ is provable from your theory iff $\varphi$ is provable from $I\Sigma_2$. Since $I\Sigma_2$ is undecidable, this means your theory is undecidable as well.
Note that there's a crucial subtlety here: when we say "$X$ is decidable" we need to specify a language. For example, the empty set is decidable as a theory in the empty language but is not decidable as a theory in the language of arithmetic by exactly the same argument above. (The same applies to "$X$ is complete.") By default, when we ask whether a theory is decidable we are speaking relative to the smallest language containing all symbols actually used in that theory, so we would indeed say "The empty theory is decidable" despite the technical ambiguity.
Note, however, that there is a difference between decidability and having a decidable extension; similarly with completeness. So we can ask:
(Note that from a consistent decidable extension we can build a consistent decidable complete extension, by a greedy algorithm.) This is really the right version of the "Godelian question." I suspect the answer is no here, but I don't immediately see the proof.