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|).$


Your Answer

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

Browse other questions tagged or ask your own question.