$\begingroup$
$\endgroup$
10
What is the complexity of the following decision problem?
- Input: a Turing machine $M$, a word $\vec{w}$, and a unary primitive recursive function $f : \mathbb{N} \to \mathbb{N}$.
- Output: "yes" if and only if $M$ accepts $w$ in fewer than $f(\vert \vec{w} \vert)$ steps.
What would be the complexity if instead of a "primitive recursive function" we consider an "arithmetical function"?
-
1$\begingroup$ What do you mean by "arithmetical"? And how is $f$ represented by a finite string so that it can be given as an input to a decision problem? $\endgroup$Emil Jeřábek– Emil Jeřábek2025年10月23日 13:30:46 +00:00Commented Oct 23 at 13:30
-
$\begingroup$ If "arithmetical" literally means "given by a formula over $(\mathbb N,0,1,+,\cdot)$", then this has clearly the same complexity as $\mathrm{Th}(\mathbb N)$. E.g., fix $M$ and $w$ that is accepted in one step, and then given a sentence $\phi,ドル let $f$ be the constant function 2ドル$ if $\phi,ドル and 1ドル$ otherwise. $\endgroup$Emil Jeřábek– Emil Jeřábek2025年10月23日 13:42:09 +00:00Commented Oct 23 at 13:42
-
$\begingroup$ What is "the same complexity as Th($\mathbb{N}$)"? $\endgroup$David Carral– David Carral2025年10月23日 15:21:01 +00:00Commented Oct 23 at 15:21
-
$\begingroup$ I have changed the requirements on the type of functin; hope that this clarifies things! $\endgroup$David Carral– David Carral2025年10月23日 15:37:24 +00:00Commented Oct 23 at 15:37
-
$\begingroup$ $\mathrm{Th}(\mathbb N)$ (true arithmetic) is one of standard benchmark problems in computability thery. It is equivalent to $\emptyset^{(\omega)},ドル but other than that, there is no simpler explanation of what "is" its complexity. There is no general way how to measure the complexity of highly noncomputable problems other than showing how they relate to other such problems. $\endgroup$Emil Jeřábek– Emil Jeřábek2025年10月23日 16:05:33 +00:00Commented Oct 23 at 16:05