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

687 questions
Filter by
Sorted by
Tagged with
45 views

### Maximal decidable Diophantine sets [closed]

Thanks to the negative solution of Hilbert's tenth problem by Matiyasevich, Robinson, Davis and Putnam we know that there can be no general algorithm for deciding if a given Diophantine equation has ...
211 views

256 views

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

This question was asked and bountied at MSE without response. Call a sentence $\varphi$ in the language of arithmetic $Q$-like iff $\mathbb{N}\models\varphi$ and $\{\varphi\}$ is essentially ...
68 views

### Post correspondence problem: Busy beaver variant

The Post correspondence problem (Wikipedia link) is to decide for $k$ pairs of strings $$(a_1,b_1), (a_2, b_2), ..., (a_k,b_k),$$ if there exists a finite sequence of numbers $c_j, 0\le j\le j_\max$ ...
41 views

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

What are the relation between Probabilistic Turing Machine and Turing Machine of every hierarchy, for instance, are the Probabilistic PDA and NPDA equivalent? the Probabilistic LBA and LBA equivalent?...
174 views

### Complexity of a combinatorial constraint

For two $k$-partitions $X,Y\in k^\omega$ of $\omega$ (seen as functions $\omega\rightarrow k$), we say $X,Y$ are almost disjoint iff $X^{-1}(i)\cap Y^{-1}(i)$ is finite for all $i<k$. Question: ...
107 views

### ITTMs with higher types

What is the complexity of Infinite Time Turing Machines (ITTMs) augmented with an initially empty set of real numbers, with the ability to add, remove, and test presence of a real number in the set? ...
490 views

### Provably undecidable number inequality?

Here is a question that popped into my head right as I fell asleep last night. I was thinking about constructions of irrational numbers, like pi. I was wondering if there are two constructions (any ...
256 views

### Transfinite algorithms

The Ford-Fulkerson algorithm is a classic algorithm that computes the maximum flow in a network. It is well-known that if irrational arc capacities are allowed, the algorithm does not necessarily ...
142 views

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

I have just written a short javascript program which, given any boolean expression with $N$ variables, completes in N "ticks" of the clock and which makes the decision. I will explain this algorithm, ...
120 views

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

It is trivial to show that Peano artithmetic ($\mathsf{PA}$) supplemented with the $\omega$-rule is complete. Joseph Shoenfield (`On a Restricted $\omega$-Rule', Bull. Acad. Polon. Sci. 7 (1959): 405–...
88 views

### Is Steiner symmetrization “Turing complete”?

This question stems from intuition so it is a little soft. It concerns performing computation using transformations on sets. The idea is that a rearrangement like Steiner symmetrization might be "...
423 views

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

This question was asked and bountied at MSE, with no response. Many years ago I ran into the following proof of Godel's first incompleteness theorem (here $T$ is an "appropriate" theory of ...
212 views

### The fastest growing function of given complexity

Let $f$ be a computable function $\mathbb{N} \to \mathbb{N}$ be a computable function. Since a program of a computable function is a finite object we can define plain Kolmogorov complexity of $f$ (we ...
81 views

### Fixed points of recursive functions with finite range

Let $\phi$ be a programming system satisfying the UTM Theorem (i.e., $\phi$ is a $2$-ary partial recursive function such that the list $\phi_0,\phi_1,\ldots$ includes all $1$-ary partial recursive ...
64 views

### Are the very hyperlows closed under join?

Call $X$ very hyperlow if $\mathcal{O}^X \le_T \mathcal{O}$, where $\mathcal{O}$ is your favorite $\Pi^1_1$-complete set. Note: Turing reducibility, not hyp-reducibility. Observe that this is a (...
228 views

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

(I previously asked a similar question on cstheory.SE; I have simplified the notion, which presumably changes it but does not change the key properties I'm interested in.) This is about a strange ...
155 views

156 views

156 views

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

There is a folklore correspondence between topology as semi-decidability amongst computer scientists, which is explained in places like: The monograph Synthetic Topology: of Data Types and Classical ...
280 views

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

Suppose $\mathfrak{U}$ is a variety of groups. Let's define $F_n(\mathfrak{U})$ as relatively free groups in $\mathfrak{U}$. Suppose $G \in \mathfrak{U}$ is a finitely generated group. We call $G$ ...
Given an index set $A$ of indices that compute some (class of) structures such that $A$ is complete in the class $\Pi^0_n$ in the arithmetical hierarchy, let’s say we want to determine the ...