1
$\begingroup$

Given an enumeration of register machines $R_n$ that take a single natural number as input, and a constant $k$, the function $f$ is defined as:

$$ f(n) = \begin{cases} 1 & \exists m \text{ such that } R_n(m) \text{ halts in } k \text{ steps} \\ 0 & \text{otherwise} \end{cases} $$

I'm trying to show that this function is not recursive, but am unsure of how to go about doing so? If anybody could give me any advice I'd be very grateful.

$\endgroup$

0

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.