Publication | Closed Access
Diagonally Non-Computable Functions and Bi-Immunity
14
Citations
10
References
2013
Year
Theory Of ComputingNon-computable FunctionsSymmetric FunctionEngineeringComputability TheoryEnumerable SubsetComputational Model TheoryComputational ComplexityComputer ScienceDiscrete MathematicsSet ATuring MachineNoncomputable Function
Abstract We prove that every diagonally noncomputable function computes a set A which is bi-immune, meaning that neither A nor its complement has an infinite computably enumerable subset.
| Year | Citations | |
|---|---|---|
Page 1
Page 1