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

**2**

**1**answer

### How to compare three supremums of ordinals eventually writable by Ordinal Turing Machines?

**6**

**3**answers

### Relationship between provable in $RCA_0$ and effectively true

**3**

**0**answers

### Empty preimage under homomorphism of finitely presented groups with decidable word problems

**11**

**1**answer

### Does every countable set of Turing degrees have an upper bound, without AC?

**6**

**0**answers

### Rational point oracle for smooth projective varieties

**4**

**1**answer

### Is decidability reducible to unique decidability (perhaps in multilinear polynomial situations)?

**0**

**0**answers

### Where does intuitionistic predicate logic live in the arithmetical hierarchy?

**2**

**0**answers

### Can we have a “very strong” cone phenomenon in the Turing degrees (and a related question)?

**6**

**1**answer

### Are there structures in a finite signature that are recursively categorically axiomatizable in SOL but not finitely categorically axiomatizable?

**4**

**2**answers

### How large is the supremum of halting times of Infinite Time Turing Machines, assuming that halting times are bounded and inputs are arbitrary?

**12**

**1**answer

### Descriptive set theory for computer scientists?

**6**

**0**answers

### “Relative plausibility” of some infinitary theories

**2**

**0**answers

### Decidable equality for computable functions $\mathbb{N}\to\mathbb{N}$

**3**

**0**answers

### Variation in decidability of diophantine equations with field extension

**3**

**1**answer

### Ordinal numbers reachable by primitive recursive ordinal functions in omega

**2**

**1**answer

### Busy beaver sequence for a simple tag-like system

**1**

**2**answers

### Is there an analogue of the Lost Melody Theorem in ordinary recursion theory and if not, why not?

**1**

**0**answers

### Why doesn't $\mathsf{B}\Sigma_2$ hold in $\mathsf{RCA}_0$?

**3**

**0**answers

### Is a function growing faster than any computable function necessarily independent of ZFC?

**7**

**1**answer

### Independence of $\Pi^1_1$-induction from ATR$_0$

**0**

**0**answers

### Bijectively parametrize non-negative integers by binary sequences

**4**

**0**answers

### Are there any 1-decidable algebraic extensions of $\mathbb{Q}$ which are not decidable?

**10**

**1**answer

### What is the Turing degree of the monadic theory of the real line?

**2**

**0**answers

### Is this variant of bitwise cyclic tag Turing-complete? [closed]

**5**

**0**answers

### What is known about these “explicitly represented” spaces?

**4**

**1**answer

### Uniform incomparable consistency strengths

**2**

**0**answers

### Good notation for finite partial functions from $\omega$ to 2

**0**

**1**answer

### Algorithmically decide if an algorithm has optimal time complexity [closed]

**5**

**1**answer

### Formula that requires a higher complexity to be proved

**3**

**0**answers

### How to solve special Diophantine equation systems (which one can solve by hand) with the computer?

**2**

**1**answer

### Uncomputability of a function based on the Busy Beaver function

**7**

**1**answer

### How big is the least non-$\Sigma^1_1$-pointwise-definable ordinal?

**-1**

**1**answer

### Big-Oh bound of a recursive function with two variables [closed]

**2**

**1**answer

### Arithmetic non-trivial 2-l.u.b

**9**

**0**answers

### What logic characterizes relative intrinsic complexity in set recursion?

**0**

**0**answers

### Proof that $\omega_1^{CK}$ is admissible

**8**

**1**answer

### Can two versions of $\omega_1^{CK}(\mathsf{Ord})$ ever coincide?

**1**

**1**answer

### Computable in $\omega$-REA degree but not double jump of finitely many columns

**10**

**1**answer

### What is known in general about the liquid transfer problem?

**15**

**2**answers

### Are the vertical sections of the Ackermann function primitive recursive?

**4**

**2**answers

### Infinite descending chain of Turing jumps with equality

**1**

**1**answer

### Is a cohesive set always an almost subset of a co-simple set?

**5**

**2**answers

### Checking for finite fibers in hash functions

**4**

**1**answer

### Is there a “listable” structure of computable dimension $\omega$?

**3**

**1**answer

### Does “productive = dimension $\omega$” for computable structures?

**-1**

**1**answer

### ITTM busy beaver function VS Rayo's function

**2**

**1**answer

### Generality of construction for $\omega$-REA arithmetic degrees

**3**

**1**answer

### What is the strength of the second-order statement 'an uncountable closed set in $\mathbb{R}$ has a limit point'?

**5**

**3**answers

### Is there a quantum analog of Kolmogorov Complexity?

**5**

**1**answer