My question is a follow-up question to this one: How to show that a function is computable?
The original question was:
Is the following function $$g(x) = \begin{cases} 1 & \mbox{if } \phi_x(x) \downarrow \mbox{or } x \geq 1 \\ 0 & \mbox{otherwise } \end{cases}$$ computable?
The accepted answer was that this function is computable because it is either the constant 1 function or the function that is 1 everywhere except on input 0.
According to my professor at university, this answer is in fact correct. But I don't understand the intuition behind it.
As far as I know, “computable” means (amongst other things) that there is an algorithm that actually can compute the function. I don't really get how such an algorithm would look in this case. Obviously, if $x\geq 1$, the algorithm can immediately return 1. But if the input is 0, the algorithm would have to simulate $\phi_0(0)$. If $\phi_0$ terminates on input 0, then the algorithm can return 1. But if $\phi_0$ doesn't terminates on input 0, the algorithm will run forever and never return 0.
So my understanding of the concept “computable” is in conflict with its actual meaning. Can someone explain where the error in my reasoning lies?
What you have there is a definition of a function $g$, not an algorithm for computing it. The definition is written in the language of mathematics, where "$a$ or $b$" is equivalent to "$b$ or $a$", not in a programming language, where "$a$ or $b$" might mean "first evaluate $a$, and if it's true then the statement is true, otherwise evaluate $b$ and let that be the truth value of the statement". In particular, the first case of the definition doesn't mean "first compute $\varphi_x(x)$, and if it halts, see if $x\ge 1$; if so, return $1$".
Relative to whatever formalism we adopt — Turing machines, lambda calculus, transformational grammars, etc. — $\varphi_0(0)\!\!\downarrow$ has some truth value $tv$. We may already know what it is (it halts quickly, or provably it doesn't halt), we may not yet know (it hasn't halted yet), or we may never find out (because it really is false). In any case, $g$ is equal to one of two computable functions, each of which has a trivial algorithm that doesn't give a hoot about about $\varphi_0$ and how it behave on input $0$. Whichever function $g$ is, it's computable. Just which one it is depends upon $tv$, so we may not be able to say which function $g$ actually is.
This is reminiscent of the very nonconstructive proof that there are irrationals $x,y$ such that $x^y$ is rational: if ${\sqrt 2}^{\sqrt 2}$ is rational, let $x=y={\sqrt 2}$; otherwise, let $x={\sqrt 2}^{\sqrt 2}, y = {\sqrt 2}$. (In fact, the fun has been spoiled: someone has proved that ${\sqrt 2}^{\sqrt 2}$ is irrational. So perhaps ${\sqrt 3}^{\sqrt 2}$, going forward :) Similarly, the definition of $g$ is not constructive: it uses the law of excluded middle in an essential way. The proof that $g$ exists (i.e. that it's even well-defined) is a nonconstructive existence proof of an algorithm, not an algorithm.