# 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.

**0**

**0**answers

### Maximal decidable Diophantine sets [closed]

**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*

**9**

**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

### Do all non-computable functions grow faster than computable functions?

**4**

**1**answer

### Which ordinal is larger, the supremum of ordinals writable by iterated Infinite Time Turing Machines or the smallest $\Sigma_2^1$-reﬂecting ordinal?

**3**

**1**answer

### Is checking whether a compact $\Pi^0_1$-class is nonempty $\Sigma^1_1$-hard?

**27**

**7**answers

### Decision problems for which it is unknown whether they are decidable

**2**

**0**answers

### When can all elements of $[A\to B]$ can be represented as computable functions?

**1**

**0**answers

### Existence of limit computable map

**3**

**1**answer

### Is self-escaping without self-dominating possible?

**5**

**0**answers