https://wiki.computability.org/ 2026-05-09T13:45:23+00:00 https://wiki.computability.org/ https://wiki.computability.org/lib/tpl/bootstrap3/images/favicon.ico text/html 2025-02-12T10:32:28+00:00 lpatey (lpatey@undisclosed.example.com) https://wiki.computability.org/theorem:rice?rev=1739356348&do=diff Rice's theorem Rice's theorem is a fundamental result in computability theory that concerns the properties of recursively enumerable languages. It states that every non-trivial property of the language recognized by a Turing machine is undecidable. \( P \)\( P \)\( P \)\( P \)\( P \)\( P \) text/html 2025-02-12T10:21:33+00:00 lpatey (lpatey@undisclosed.example.com) https://wiki.computability.org/start?rev=1739355693&do=diff Computability theory wiki Welcome to the Computability theory wiki, a comprehensive resource dedicated to the study of computability and recursion theory. This wiki aims to provide clear and rigorous definitions of core terminology, as well as structured mini-courses to facilitate learning at different levels. See the text/html 2025-02-12T10:19:42+00:00 lpatey (lpatey@undisclosed.example.com) https://wiki.computability.org/turing_degree?rev=1739355582&do=diff Turing degree The concept of Turing degree is fundamental in computability theory and provides a way to classify the relative complexity of undecidable problems. Two sets of natural numbers have the same Turing degree if they are Turing equivalent, meaning each can be computed from the other using a Turing machine with an oracle for the set.\( A \)\( \deg(A) \)\( A \)\( A \)\( B \)$$ A \leq_T B $$\( A \)\( B \)\( A \leq_T B \)\( B \leq_T A \)\( A \)\( B \)\( A \equiv_T B \)\( \leq_T \)\( \mathb… text/html 2025-02-12T10:18:13+00:00 lpatey (lpatey@undisclosed.example.com) https://wiki.computability.org/topic:sets_sequences_reals?rev=1739355493&do=diff Sets of integers, binary sequences and real numbers In computability theory, there is a well-established tradition of identifying three distinct mathematical objects: sets of integers, infinite binary sequences, and real numbers. This identification is often useful, but it is important to recognize that the corresponding topological spaces are different and lead to distinct mathematical properties.\( A \subseteq \mathbb{N} \)\( n \)\( n \in A \)\( X \in 2^{\mathbb{N}} \)\( [0,1] \)\[ X = 0.X_0X…