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.
974
questions
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)$ ...
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 ...
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.
...
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, ...
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{...
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 ...
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. ...
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 ...
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 ...
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 ...
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 ...
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 ...
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?
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 ...
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 ...
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"...
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 ...
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 ...
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 ...
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. ...
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})$. ...
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 ...
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-...
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$: ...
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 $\...
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 ...
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 ...
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 ...
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}((...
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 ...
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 ...
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 ...
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 ...
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 = \...
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 ...
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 ...
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 \...
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 ...
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 ...
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 ...
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 ...
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?
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, ...
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....
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 ...
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 ...
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$.
...
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}\...
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 ...