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.

Filter by
Sorted by
Tagged with
8 votes
1 answer
998 views

Why don't Zeilberger and Gosper's algorithms contradict Richardson's theorem?

Richardson's theorem proves that whether an expression A is equal to zero is undecidable. A is in this case an expression, constructed from $x,e^x,\sin(x)$ and the constant function $\pi$ and $\ln(2)$ ...
Martin Clever's user avatar
8 votes
2 answers
491 views

History of forcing over admissible sets

In his paper "Forcing in admissible sets", Ershov writes In unpublished lectures given at Novosibirsk State University in 1976-1977 on the theory of admissible sets, the author showed that it is ...
Noah Schweber's user avatar
8 votes
3 answers
1k views

"Rice (like) Theorem" for primitive recursive functions?

As primitive recursive (PR) functions seem to be so important (see for instance Kleene normal form Theorem) we may expect that many decision questions related to PR functions are undecidable. ...
Armando Matos's user avatar
8 votes
1 answer
1k views

Can a Hamkins infinite time Turing Machine with infinite Super Turing jumps (from higher type oracles) get the power to decide $\Sigma_1^2$ sets?

Hamkins showed that his infinite time Turing machine has the power to decide some $\Delta_2^1$ sets. I wonder if some modifications of the machine could be made to reach level $\Sigma_1^2$ sets, or, ...
Wolphram jonny's user avatar
8 votes
2 answers
479 views

Comprehension axiom that helps in the opposite direction

Usually, having more comprehension axiom means the more you can prove. We wonder if the converse can be the case. Is there a natural problem $\mathsf{P}$ so that $\mathsf{P}+\neg(\Gamma-\mathsf{...
Jiayi Liu's user avatar
  • 909
8 votes
2 answers
732 views

Recursively enumerable sets as range sets of functions in Grzegorczyk-hierarchy

It is well known that recursively enumerable sets can be defined (among many other equivalent alternatives) as the range sets of primitive recusive functions (except for the trivial case of the empty ...
boumol's user avatar
  • 788
8 votes
2 answers
731 views

Paul Cohen on genesis of method of forcing and mathematical similarities

We have on record Paul Cohen's comments on being inspired by issues of formalizing algorithms in number theory (this needs to be verified as per comment) as well as related remarks on computability. ...
Mikhail Katz's user avatar
  • 15.1k
8 votes
3 answers
1k views

Undecidable problems in geometry

Are there any (many) algorithmically undecidable problems in computational (combinatorial/discrete) geometry? Update: the Wang tiles answer the question with "any". (I have somewhat overlooked to ...
8 votes
2 answers
2k views

Is simply typed lambda calculus with fixed-point combinator Turing-complete?

There are many sources cite that simply typed lambda calculus extended with fixed-point combinator is Turing complete. For example, Does there exist a Turing complete typed lambda calculus? or the ...
kittyphon's user avatar
8 votes
3 answers
265 views

Relationship between provable in $RCA_0$ and effectively true

Question: What is the relationship between provability in $RCA_0$ and effectively true? In other words: Given a problem, if a statement asserting the existence of a solution of the problem is provable ...
peterEller's user avatar
8 votes
1 answer
274 views

Correspondence between proof-theoretic ordinals and fast growing functions?

For theories with well known proof-theoretic-ordinals, (what) is there a correspondence between their proof-theoretic-ordinal and (ordinal indexed families of?) fast growing functions provable total ...
Łukasz Lew's user avatar
8 votes
1 answer
470 views

What is the Turing degree associated with an ultrafilter $U$?

I asked Turing degree of a turing machine with access to an (arbitrary) nonstandard integer, not thinking about the possiblity that this could depend on the model used. The question was not formulated ...
Christopher King's user avatar
8 votes
2 answers
460 views

Does forcing with recursively pointed perfect trees add a Turing degree that is minimal over $V$?

A tree $T$ on $\omega$ is recursively pointed if it is recursive in each of its branches. We can consider a variant of Sacks forcing where the conditions are recursively pointed perfect trees ordered ...
Trevor Wilson's user avatar
8 votes
1 answer
380 views

Good source for admissible set theory?

So I need to writeup some old results of Harrington's which imply various results about admissible ordinals. I've never really learned admissible recursion theory so what's a good reference?
Peter Gerdes's user avatar
  • 2,551
8 votes
1 answer
454 views

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

There's a large countable ordinal which has cropped up (as a lower bound!) in a computable structure theory problem I'm playing with. At present I don't really understand how big it is, and I'm ...
Noah Schweber's user avatar
8 votes
1 answer
412 views

Which reals are "hyperarithmetic modulo ordinals"?

The context for this question is the theory ZFC + a measurable cardinal, although answers not in this context would also be interesting to me. In a project I'm working on, the following class of ...
Noah Schweber's user avatar
8 votes
1 answer
542 views

Proof-theoretic ordinals: inevitable consistency?

There are various different notions of the proof-theoretic ordinal of a theory; most of these are "notation-dependent" in that they're only nontrivial once we restrict attention to a class of "natural"...
Noah Schweber's user avatar
8 votes
1 answer
1k views

Recursion theory from the standoint of category theory

It is (I believe) a very easy exercise to prove that the general recursive functions over the natural number object $N$ form a category. But what sort of category is it? From the fact that one can ...
Thomas Benjamin's user avatar
8 votes
1 answer
344 views

Decidable theories with arbitrary complexity

Are there complete finitely axiomatizable first order theories (with equality) with arbitrarily high computational complexity? Here, arbitrarily high (computational) complexity means that for every ...
Dmytro Taranovsky's user avatar
8 votes
1 answer
307 views

Is every total computable function definable by a normalizing lambda term?

$\newcommand{\nat}{\mathbb{N}}$ $\newcommand{\then}{\ \Longrightarrow\ }$ A partial function $f : \mathbb{N} \to \mathbb{N}$ is said to be $\lambda$-definable if there is a term $F \in \Lambda$ such ...
Andrew Polonsky's user avatar
8 votes
1 answer
335 views

The equality problem between conjugate group elements

The Novikov--Boone Theorem, which is perhaps the archetypal local unsolvability result in group theory, states existence of a finitely presented group whose word problem is recursively unsolvable. ...
Daniel Moskovich's user avatar
8 votes
3 answers
726 views

Natural statements independent from true $\Pi^0_2$ sentences

I am looking for sentences in the language of first order arithmetic ($0,1,+,\cdot,\leq$) which are independent from $\Pi^0_2$ consequences of true arithmetic $\Pi^0_2\text{-}\mathsf{Th}(\mathbb{N})$. ...
Kaveh's user avatar
  • 5,362
8 votes
1 answer
571 views

a proof that L_min is not in coRE?

Define $L_{min}$ to be the language of all minimal Turing machines, in some standard encoding. (A Turing Maching is minimal if it has the shortest encoding among all the TMs recognizing the same ...
Aryeh Kontorovich's user avatar
8 votes
1 answer
308 views

Martin-Löf randomness relative to a $\Delta^0_2$-representation of a real

I have a question which I already asked on a more specialized site (http://logicblogfrontend.hoelzl.fr/), but perhaps M.O. will allow me to reach a wider range of experts. Suppose that $X$ is Martin-...
Laurent Bienvenu's user avatar
8 votes
1 answer
194 views

A well-behaved $A$ that is almost contained in every element of some filter for a countable arithmetically closed family $\mathfrak X$

The question has relevance for constructing Scott sets with certain extra desirable properties. Suppose that $\mathfrak X$ is a countable arithmetically closed family of subsets of $\mathbb N$: ...
Victoria Gitman's user avatar
8 votes
2 answers
615 views

Enumerating levels of Grzegorczyk-hierarchy

Grzegorczyk has divided the class of primitive recursive functions to Grzegorczyk-hierarchy by their rate of growth. In this hierarchy $E_i\subset E_{i+1}$ and the subset-relation is strict. Also $\...
user avatar
8 votes
1 answer
345 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 ...
Noah Schweber's user avatar
8 votes
1 answer
716 views

List of finitely presented groups with undecidable word problem

Is there any reasonably updated list of (representative) examples of finitely presented groups with undecidable word problem? By "representative" I mean "avoiding obvious redundancy", i.e. examples ...
suitangi's user avatar
  • 333
8 votes
2 answers
563 views

Coiling Rope in a Box: Decidable?

Is the problem Coiling Rope in a Box decidable? To be specific, is this decidable? Given $L > 0$ and $r \in (0,\frac{1}{2})$, both rational, can a rope of length $L$ and radius $r$ fit ...
Joseph O'Rourke's user avatar
8 votes
1 answer
349 views

How long does the slow inefficient algorithm for computing the product in classical Laver tables take?

Let $(A_{n},*)$ denote the $n$-th classical Laver table. Let $X_{n}$ be the set of all finite sequences of elements from $A_{n}$. Define a function $E_{n}:X_{n}\rightarrow X_{n}$ by letting $E_{n}((...
Joseph Van Name's user avatar
8 votes
1 answer
257 views

What is known about these "explicitly represented" spaces?

Apologies if this is too low-level. A related question that I asked on the Math Stack Exchange got no answers after a year, so I thought it might be better to ask this one here. The standard approach ...
Robin Saunders's user avatar
8 votes
0 answers
433 views

Alternative definition of Kolmogorov complexity

In Kikuchi's paper Kolmogorov complexity and the second incompleteness theorem the Kolmogorov Complexity (KC) of $x$ is defined as $$ K(x) = \mu e (\varphi_e(0) \simeq x) \, . $$ This seems to give ...
Jori's user avatar
  • 179
8 votes
0 answers
219 views

Large "computably un-simplifiable" computable well-orderings

Question Suppose $A,X$ are computable well-orderings. Say that $A$ is $X$-unsimplifiable if there is no computable well-ordering $B$ whose ordertype is strictly less than that of $A$ but such that ...
Noah Schweber's user avatar
8 votes
0 answers
262 views

Natural examples of recursive pseudowellorderings

Question: What are some natural examples of recursive pseudowellorderings? By natural, I mean in the style of reasonable ordinal notation systems as opposed to dependent on a Gödel numbering or an ...
Dmytro Taranovsky's user avatar
8 votes
0 answers
151 views

Is every total computable function definable by a strongly total lambda term?

Every computable (total) function $f : \mathbb{N} \to \mathbb{N}$ is definable in untyped pure lambda calculus in the sense that there is a term $F$ such that, for every Church's numeral $c_n = \...
Valery Isaev's user avatar
  • 4,410
8 votes
0 answers
183 views

Using van de Wiele's characterization as a definition?

This fall I'm teaching a class on generalized computability theory (broadly construed). One thing I want to talk about briefly is E-recursion. Now, E-recursion is generally defined in terms of the ...
Noah Schweber's user avatar
8 votes
0 answers
398 views

The cone property in the enumeration degrees

A Borel partial order is the partial order corresponding to a Borel preorder of some Polish space. For example, the Turing and enumeration degrees, $\mathcal{D}$ and $\mathcal{E}$ respectively, are ...
Noah Schweber's user avatar
8 votes
0 answers
383 views

The reals in $L$

Assume "$0^\#$ exists". We know that $0^\#$ is a $\Pi^1_2$-singleton. That means, there is a Shoenfield tree $S$ on $\omega \times (\omega \times \omega_1)$ so that $$x = 0^\# \leftrightarrow S_x \...
Yizheng Zhu's user avatar
7 votes
3 answers
2k views

Decidable but nonrecursive sets

Until recently, I believed that recursive=decidable, subscribing to this Wikipedia quote: "In computability theory, a set is decidable, computable, or recursive if there is an algorithm that ...
Joseph O'Rourke's user avatar
7 votes
5 answers
16k views

Prove a function is primitive recursive

Hey, I'm taking a course in computability theory, but I'm struggling with primitive recursion. More specifically we are often asked to prove that some arbitrary function is primitive recursive, but I ...
Peter Marsh's user avatar
7 votes
5 answers
1k views

(reference request) Chaitin's constant is incompressible

I've been looking for a full, detailed proof that Chaitin's constant is incompressible, i.e. there is a universal constant $c$ such that every program writing first $n$ digits of $\Omega$ has length ...
Wojowu's user avatar
  • 27.4k
7 votes
2 answers
609 views

Ideals generated by Turing independent sets

Recall that $X \subseteq 2^{\omega}$ is Turing independent if no $y \in X$ is computable from the Turing join of any finite subset of $X \setminus \{y\}$. Question 1. Can we construct a Turing ...
Fiona's user avatar
  • 71
7 votes
3 answers
3k views

Is there an algorithm that can "reverse engineer" a Regular Expression?

Given a Regular language (represented as a black box to which one can apply inputs and get 0/1) Is there an algorithm that can find a finite deterministic automaton that produces that language?
Golan's user avatar
  • 73
7 votes
2 answers
1k views

Does permission always work?

Suppose $g$ is a total computable injective function and $f$ is a total computable function satisfying $$g(x)<f(x)$$ for all sufficiently large $x$. Then we have $ran(f)\le_Tran(g)$; basically, ...
Noah Schweber's user avatar
7 votes
3 answers
472 views

Is there a constructive version of internal set theory?

Is there a theory T such that: T includes all the axioms of CZF. T includes the Idealization, Standardization, and Transfer schemas from IST. Every axiom of T is a theorem of IST. T has Church's rule....
Christopher King's user avatar
7 votes
2 answers
845 views

Are computable models sufficient?

What I mean is this. By downward Lowenheim-Skolem theorem, first-order formula Q is a always true iff it is true in every countable structure. But is there some first-order formula Q which is true in ...
Sergei Tropanets's user avatar
7 votes
1 answer
2k views

Ackermann function in the Primitive recursive arithmetic

Hello. I study primitive recursive arithmetic and have the following questions. 1) Is it possible to express in the PRA that Ackermann function is total? 2) If yes, is such expression decidable in ...
Dan's user avatar
  • 1,288
7 votes
2 answers
636 views

Topological tameness beyond the Gandy-Harrington topology

The Gandy-Harrington topology on $\omega^\omega$ is the topology generated by all lightface $\Sigma^1_1$ sets; that is, all sets which are continuous-in-the-usual-sense images of $\omega^\omega$. ...
Noah Schweber's user avatar
7 votes
2 answers
586 views

Is there a noncomputable set which can be described by a probabilistic Turing machine with bounded error?

Does there exist any noncomputable set $A$ and probabilistic Turing machine $M$ such that $\forall n\in A$ $M(n)$ halts and outputs $1$ with probability at least $2/3$, and $\forall n\in\mathbb{N}\...
Alex Mennen's user avatar
  • 2,090
7 votes
1 answer
427 views

Can ITTM recognize a non-measurable set?

Throughout the question ITTM refers to Hamkins' infinite Turing machines, though I will be interested in results related to stronger models. Recently I was wondering, is it consistent that there is ...
Wojowu's user avatar
  • 27.4k

1
4 5
6
7 8
20