1
$\begingroup$

Before I start with my question, I want to state some notation I am using. I fix some arbitrary but fixed enumeration of Turing Machines (TMs) and denote with $\Phi_i : \mathbb{N}\to\mathbb{N}$ the function that is computed by the $i^\text{th}$ TM in this enumeration. Furthermore $\Phi_i(x) \downarrow$ denotes that the computation of $\Phi_i(x)$ terminates with some result $y$, i.e., $\Phi_i(x) = y$. Furthermore, $\Phi_i(x) \uparrow$ denotes that the computation of $\Phi_i(x)$ never terminates.

I know that the following function is not computable: $$ f(x) = \begin{cases} 1 & \text{if } \Phi_x(x)\downarrow \\ 0 & \text{otherwise} \end{cases} $$

Now, suppose we fix some $n \in \mathbb{N}$ and define: $$ h(x) = \begin{cases} 1 & \text{if } \Phi_x(x)\downarrow \text{ and } x \le n\\ 0 & \text{otherwise} \end{cases} $$

I found some lecture notes which state that $h$ is computable because it is the characteristic function of a recursive set (because it is finite) and is therefore computable. Is this claim correct?

If $h$ is actually computable I can't think of an algorithm because one simply can't decide if $\Phi_x(x)$ diverges to return $0$ in the case that $x \le n$.

$\endgroup$
1
5
$\begingroup$

Fix a value of $n$. For $b \in \{0,1\}^n$, consider the following algorithm $A_b$:

If $x \leq n$ then output $b_x$, otherwise output $0$.

Clearly one of the $2^n$ algorithms of the form $A_b$ computes your function $h$, hence $h$ is computable.

$\endgroup$
10
  • $\begingroup$ Thank you, that clears it up. I was confused by the question where I found this problem because it says below: "If $h$ is computable give an informal algorithm" and this was the part where I couldn't see how to describe such an algorithm. $\endgroup$ – hetzi Jan 18 at 10:24
  • $\begingroup$ @hetzi Don't confuse "there exists" and "we can find" or even "if we found it, we could prove it correct". ;) IIRC, I think someone computed an upper limit on how big an n we could prove the corresponding h is correct given the bits required to describe the axioms used to describe Turing Computability or something like that. $\endgroup$ – Yakk Jan 18 at 16:11
  • $\begingroup$ @Yakk There's no upper limit on n - just choose a different enumeration. For instance, I could construct a family of Turing Machines that I know halt, and say that they're the first n machines in the enumeration, and then past that return to some other enumeration. $\endgroup$ – Spitemaster Jan 18 at 18:47
  • $\begingroup$ @Spitemaster If the limit is a function of the enumeration (the bits required to describe the enumeration), and the enumeration is complete, there is a limit to how deep you can pump out always-halting turing machines and easy-to-determine-they-halt turing machines and still reach every turing machine. I should find the actual result however; it was connected to producing a constant where the number of digits you could calculate was bounded by the complexity of your axiomatization system, and I definitely am skipping over details and nuances here. $\endgroup$ – Yakk Jan 18 at 19:09
  • $\begingroup$ @Yakk That can't be correct; consider the family of machines which have n states and each state except the nth writes "1", moves right, and transitions to the next state. The nth state halts. It's pretty clear that I can generate any finite n machines. Describing the enumeration is simple; it's just that family up to n, then any other enumeration skipping machines of this family up to n. I don't know how many bits that requires. I suppose the limit would be related to the description of n - but in that case, the sequence [1..., 0...] (with n 1s) is provably correct without any difficulty. $\endgroup$ – Spitemaster Jan 19 at 3:15
3
$\begingroup$

The subtle idea of computability of finite sets is that we don't necessarily need to know which TM machine actually decides that set or how it is internally. We just need to know that some TM decides that finite set.

Given $n$, there are (infinite) Turing Machines that decides every subset of $\{0,1,\dots{},n\}$.

You don't know which one is the set for which $h(\cdot)=1$, but you know that one of them is.

The definition of recursive/decidible set does not mention the fact that its characteristic function must have some "semantics" regarding some problem, but it concerns only on the fact that the 1 pre-image of that function is precisely that set.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.