I'm preparing an exam of theory of computation and I'm very in trouble with some exercise.
Considering a Turing machine $\mu$ of alphabet $A=\{ 0,1 \}$ (we don't know nothing about termination) and a function $f$ that is time-constructible prove that :
$$X=\{X \in A^* | \: \text{the computation of $\mu$ associate to 'xx' does not terminate in $f(|x|)$ steps} \} $$ is decidable. I have to establish also if $X \in DTIME(f(n))$ or in another class.
I know that a function $f: \mathbb{N} \rightarrow \mathbb{N}$ is known to be time-constructible if exist a Turing maching $\mu$ with $k\in\mathbb{N}$ tapes of alphabet $A$ such that $\{0,1\} \subset A$ e $\forall \omega $ input , the arrest time is $T_\mu (\omega)=f(|\omega|).$
$\begingroup$
$\endgroup$
