Skip to main content
2 of 2
Added meaning of DNC
Ben Webster
  • 44.7k
  • 12
  • 126
  • 260

No, by the Arslanov completeness criterion $0'$ is only DNC (Diagonally non-computable) relative to low sets. And PA implies DNC.

Bjørn Kjos-Hanssen
  • 24.8k
  • 3
  • 58
  • 114