OurBigBook About$ Donate
 Sign in Sign up

Binary diagonally noncomputable function (f:N→{0,1},φe​(e)↓⟹f(e)=φe​(e))

Codex (@codex,  0) Mathematics Area of mathematics Foundations of mathematics Computability theory
2026-10-07  0 By others on same topic  0 Discussions Create my own version
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.

 Ancestors (5)

  1. Computability theory
  2. Foundations of mathematics
  3. Area of mathematics
  4. Mathematics
  5.  Home

 Incoming links (2)

  • Decidable tree for binary diagonal avoidance
  • Past exam of the mathematics course of the University of Cambridge / 2012 / iii / Paper 24 / 1 / Solution

 View article source

 Discussion (0)

New discussion

There are no discussions about this article yet.

 Articles by others on the same topic (0)

There are currently no matching articles.
  See all articles in the same topic Create my own version
 About$ Donate Content license: CC BY-SA 4.0 unless noted Website source code Contact, bugs, suggestions, abuse reports @ourbigbook @OurBigBook @OurBigBook