# Questions tagged [computability-theory]

computable sets and functions, Turing degrees, c.e. degrees, models of computability, primitive recursion, oracle computation, models of computability, decision problems, undecidability, Turing jump, halting problem, notions of computable randomness, computable model theory, computable equivalence relation theory, arithmetic and hyperarithmetic hierarchy, infinitary computability, $\alpha$-recursion, complexity theory.

**1**

**1**answer

### Computable functions with limited domains

**1**

**0**answers

### About functions primitive recursively definable using a $ \Sigma _ 1 $ oracle

**3**

**2**answers

### Cupping and capping for 0’ relative to a recursively enumerable set

**2**

**1**answer

### Does degree of jump determine degrees of relatively r.e. sets?

**2**

**1**answer

### Finding 1-generic paths through a tree $T \subseteq 2^{<\omega}$

**0**

**0**answers

### Is a countable infinite union of $\Sigma_1$ sets is $\Sigma_1$? [migrated]

**2**

**1**answer

### Is there an algorithm on an infinite time Turing machine to compute a dense subset of $M_g$ for large $g$?

**4**

**2**answers

### Is the collection of primitive recursive functions a lower set in the poset of computable functions?

**2**

**2**answers

### Is there any reasonable non-regular Gödel numbering of the language of arithmetic?

**9**

**1**answer

### Does every cofinal branch through Kleene's O compute true arithmetic?

**2**

**0**answers

### Constructing Turing degrees near $\mathcal{O}$

**3**

**1**answer

### Turing machines with all runs decidable

**8**

**1**answer

### The lattice of analogues of Robinson's $Q$

**3**

**0**answers

### Post correspondence problem: Busy beaver variant

**0**

**0**answers

### Reference about Relation between Probabilistic Turing Machine and Turing Machine of every hierarchy

**6**

**1**answer

### Complexity of a combinatorial constraint

**2**

**0**answers

### ITTMs with higher types

**3**

**2**answers

### Provably undecidable number inequality?

**8**

**1**answer

### Transfinite algorithms

**2**

**1**answer

### What is the efficiency of this algorithm which decides the answer to the Boolean satisfiability problem? [closed]

**4**

**1**answer

### Strengthening of Shoenfield's result on the recursive omega-rule

**2**

**0**answers

### Is Steiner symmetrization “Turing complete”?

**11**

**0**answers

### Where did this presentation of Godel's theorem appear?

**2**

**1**answer

### The fastest growing function of given complexity

**1**

**1**answer

### Fixed points of recursive functions with finite range

**1**

**1**answer

### Are the very hyperlows closed under join?

**1**

**2**answers

### Impredictable subsets of $\mathbb{N}$

**4**

**0**answers

### When is validity definable in $L_\alpha$?

**2**

**1**answer

### The measure of ideals generated by random reals

**5**

**1**answer

### How far does this restricted definition on $\mathcal{O}$ goes?

**2**

**1**answer

### Detecting comprehension topologically

**0**

**1**answer

### Combinatorially defined effectively closed set

**1**

**2**answers

### The “higher topology” of countable Scott sets

**0**

**0**answers

### Is every productive set not Martin-Lof random？

**1**

**1**answer

### Non-relativized, Computable and Schnor randomness w.r.t a measure

**0**

**1**answer

### Kurtz randomness and supermartingales with infinite *limit*

**10**

**0**answers

### Topology is to semi-decidability, coarse structures are to what?

**7**

**1**answer

### Does Higman's embedding theorem hold inside group varieties?

**0**

**0**answers

### Is there a standard way to relativize algorithmic complexity constructively?

**6**

**1**answer

### “Robinson arithmetic” for (some) levels of $L$?

**5**

**0**answers

### The expressiveness of functions computable on trees

**1**

**0**answers

### Does relationship between c.e.set, productive set, immune set, ML-random set exist between sets of class of other level

**8**

**0**answers

### Large “computably un-simplifiable” computable well-orderings

**3**

**1**answer

### Is the Hilbert space-filling curve bijective over computable numbers?

**7**

**0**answers

### Turing-independent joins

**0**

**1**answer

### Are all $P$-noncomputable sets $P$-random? [duplicate]

**3**

**1**answer

### Relationship between P-noncomputable and P-random sets

**3**

**0**answers

### Understanding a part of Friedberg’s Priority Argument Paper

**1**

**1**answer

### Index sets and extensional many-one reductions

**-1**

**2**answers