Represent a nonnegative integer by the Church numeral
A closed lambda term represents a partial computable function if, on inputs in its domain, reduces to the Church numeral of the value, and on other inputs it produces no Church numeral. We use untyped lambda calculus and normal-order beta reduction.
First every primitive recursive function has such a representation on all inputs. The zero function is represented by a constant , the projection functions by , and the successor function by
For function composition in recursion theory, substitute the represented inner functions into the represented outer function:
These constituent functions are total, so there is no undefined argument to be discarded.
For primitive recursion, use Church Booleans and Church pairs:
If represent the total functions defining a recursion, put
and
After iterations the Church pair contains the counter and the recursively computed value at , by mathematical induction. Thus this lambda definition of primitive recursion by pair iteration represents the recursion. A structural induction for primitive recursive functions now represents every primitive recursive function.
To pass to arbitrary partial computable functions, use the Kleene normal form theorem in the following form: for every , there are total primitive recursive functions such that
with undefined precisely when no such exists. The predicate checks codes of valid finite halting histories for the chosen program; extracts their common output. This expresses unbounded minimization of a total predicate, so no earlier undefined test can interfere with the search.
Let be the represented total functions. The Church numeral zero test and a fixed-point combinator are
Define the search lambda term
All displayed abbreviations expand to finite closed lambda terms; stands for the fixed finite tuple of input variables. Because , normal-order beta reduction tests . At the first successful test the Church Boolean selects , which reduces to the correct Church numeral. The unused recursive branch is discarded.
If no test succeeds, every finite search step returns to another head search, never exposing a numeral. The term has no head normal form and hence cannot be beta equivalent to a Church numeral. This last point is why the output operation occurs inside the successful branch: simply applying a possibly argument-discarding outer function to a divergent search would not justify undefinedness. Therefore every computable function is representable, including partial computable functions with their correct undefined inputs:
A many-one reduction is a total computable function such that
A Turing reduction is an oracle machine which, with membership oracle , halts on every input and computes the indicator function . It may make finitely many adaptive queries on each input. A many-one reduction gives a Turing reduction by a single query, but Turing reducibility allows more general procedures.
The Friedberg–Muchnik theorem states that there are computably enumerable sets with incomparable Turing degrees:
Here is a finite-injury priority construction proving it. Effectively enumerate all Turing functionals . Arrange the requirements in the priority order
Equality would require the Turing functional to be total and give the correct bit at every input; one disagreement or one undefined input defeats it.
Start with and enumerate elements without ever removing them. A strategy has a private witness, a flag recording whether it has acted, and a restraint on its oracle. Every new witness is larger than every previously assigned witness and every current higher-priority restraint. Retired witnesses are never reused. The only possible enumeration of a witness is by its owner, so an unacted witness remains outside its target set.
The strategy for chooses a witness and waits for a stage at which the bounded simulation gives
On seeing this, put into , declare the strategy acted, and impose restraint on , where is the oracle use: one more than the largest queried number, or zero if there were no queries. Initialize every lower-priority strategy, discarding its current witness, acted flag and restraint. An acted strategy does nothing further until initialized. The strategy for is identical with interchanged. Waiting specifically for zero is enough: if the eventual output is nonzero while the witness stays out, it already disagrees with the target indicator function.
For a completely effective schedule, at stage visit the first strategies in priority order. Assign an unassigned witness when visited. Simulate each unacted strategy's computation for at most steps with the current finite oracle. If some strategy can act, perform the first such action and end the stage; otherwise end after all visits. All steps are finite and algorithmic, so the limiting are computably enumerable sets.
Every lower-priority enumeration respects higher-priority restraints. When its witness was chosen it lay above these restraints. Any subsequent action of a higher-priority strategy would have initialized it, so its current witness remains safe to enumerate. The initialization of all lower strategies also removes their obsolete restraints before they can obstruct a legitimate higher-priority action.
We verify finite injury by mathematical induction on priority. The first strategy is never injured and acts at most once. If all predecessors of a strategy act finitely often, there is a last stage when a higher-priority action initializes it. It is subsequently visited, chooses its permanent witness, and acts at most once. Thus it too acts finitely often and all its lower-priority strategies suffer only finitely many injuries. The scheduling cannot starve a fixed strategy: after the finitely many higher-priority actions, all sufficiently large stages visit it.
Consider the final uninjured with witness . If it acts, then permanently, and every later lower-priority enumeration into respects its restraint. No later higher-priority action occurs. The preserved computation is therefore
If it never acts, . Were , the final computation on would halt with zero and have finite oracle use. The finitely many oracle bits it queries eventually stabilize, and a sufficiently late bounded stage simulation would see exactly this zero computation. The strategy would then act, a contradiction. Hence holds in this case too. The same reasoning proves every .
All possible Turing reductions in both directions are excluded. This proves the Friedberg–Muchnik theorem; in particular both constructed Turing degrees are noncomputable, since a computable set is Turing reducible to every oracle.

Pinned article: Introduction to the OurBigBook Project

Welcome to the OurBigBook Project! Our goal is to create the perfect publishing platform for STEM subjects, and get university-level students to write the best free STEM tutorials ever.
Everyone is welcome to create an account and play with the site: ourbigbook.com/go/register. We belive that students themselves can write amazing tutorials, but teachers are welcome too. You can write about anything you want, it doesn't have to be STEM or even educational. Silly test content is very welcome and you won't be penalized in any way. Just keep it legal!
We have two killer features:
  1. topics: topics group articles by different users with the same title, e.g. here is the topic for the "Fundamental Theorem of Calculus" ourbigbook.com/go/topic/fundamental-theorem-of-calculus
    Articles of different users are sorted by upvote within each article page. This feature is a bit like:
    • a Wikipedia where each user can have their own version of each article
    • a Q&A website like Stack Overflow, where multiple people can give their views on a given topic, and the best ones are sorted by upvote. Except you don't need to wait for someone to ask first, and any topic goes, no matter how narrow or broad
    This feature makes it possible for readers to find better explanations of any topic created by other writers. And it allows writers to create an explanation in a place that readers might actually find it.
    Figure 1.
    Screenshot of the "Derivative" topic page
    . View it live at: ourbigbook.com/go/topic/derivative
  2. local editing: you can store all your personal knowledge base content locally in a plaintext markup format that can be edited locally and published either:
    This way you can be sure that even if OurBigBook.com were to go down one day (which we have no plans to do as it is quite cheap to host!), your content will still be perfectly readable as a static site.
    Figure 5. . You can also edit articles on the Web editor without installing anything locally.
    Video 3.
    Edit locally and publish demo
    . Source. This shows editing OurBigBook Markup and publishing it using the Visual Studio Code extension.
  3. https://raw.githubusercontent.com/ourbigbook/ourbigbook-media/master/feature/x/hilbert-space-arrow.png
  4. Infinitely deep tables of contents:
    Figure 6.
    Dynamic article tree with infinitely deep table of contents
    .
    Descendant pages can also show up as toplevel e.g.: ourbigbook.com/cirosantilli/chordate-subclade
All our software is open source and hosted at: github.com/ourbigbook/ourbigbook
Further documentation can be found at: docs.ourbigbook.com
Feel free to reach our to us for any help or suggestions: docs.ourbigbook.com/#contact