Intuitive meaning of the concept “computable” 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?
 A: 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.
A: A function is not the same thing as the words used to describe it. The function is the just the mapping of inputs to outputs. That mapping can be described in infinitely many different ways. For example, the identity function could be described both as "Given $x$, output $x$", or as "Given $x$, add $5$ to $x$. Now multiply $x$ by $3$, and subtract $15$. Now divide by $3$. Output the result."
The question "is this function computable" means "does there exist an algorithm which happens to produce the same outputs as this function for all inputs", and not "does there exist an algorithm which resembles this description of the function", because you're asking about the function, not the particular description of it.
