(Un)computability of a restricted Halting Problem

Question

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

Answer 1

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.

Answer 2

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.