= Binary diagonally noncomputable function
{title2=$f:\mathbb N\to\{0,1\},\quad\varphi_e(e)\downarrow\Longrightarrow f(e)\ne\varphi_e(e)$}
A total binary-valued <function> is diagonally noncomputable if it differs from each defined diagonal value in an effective enumeration of <partial computable functions>. Nonbinary diagonal outputs are automatically different. No such <function> is computable: its own program index would contradict the defining condition. Choosing the opposite bit at every defined binary diagonal value proves existence without supplying a computable procedure.
Back to article page
