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
12
votes
1
answer
803
views
Transfinitely extending $\sf PA$ — can we get stronger than $\sf ZFC$?
Let $\sf PA$ denote the theory of natural numbers with constants $(0, 1)$ and binary operators $(+,\times)$ based on the first-order predicate calculus with equality, having the following axioms, ...
15
votes
1
answer
993
views
Higher recursion theory and reverse mathematics: What is to $\Pi^1_1$-$CA_0$ as $RCA_0$ is to $ACA_0$?
There is an extremely rich and well-understood analogy between "recursively enumerable" and "$\Pi^1_1$" – indeed, this is the starting point of metarecursion theory, and $\alpha$-...
9
votes
1
answer
839
views
Uncountable time Turing machines
When writing with a friend of mine today we came up with idea of extending ITTM concept of Hamkins and Kidder. First of all, I am familiar with one of Hamkins and Lewis results saying that every ...
9
votes
1
answer
601
views
Essential incompleteness via diophantine formulas?
Work in the first order language of number theory, consisting of the symbols $\mathbf{0}$, $\mathbf{S}$, $\boldsymbol{+}$, and $\boldsymbol{\cdot}$, and let $Q$ denote Robinson's arithmetic.
By a ...
2
votes
3
answers
977
views
An established proof in Wang Tile which I doubt
When I was reading the paper:
Wang, Hao. "Notes on a class of tiling problems." Fundamenta Mathematicae 82.4 (1975): 295-305.
from http://matwbn.icm.edu.pl/ksiazki/fm/fm82/fm82119.pdf
I could not ...
7
votes
1
answer
451
views
Demuth's theorem in set theory
I am quite sure the following fact must have been known for set theorists, though I could not find it anywhere.
If $r$ is random over $L$ and $x\in L[r]\setminus L$, then there must be some real $r_0$...
11
votes
0
answers
366
views
Infinite time game of life
Today in a talk with a friend of mine I had an idea of extending cellular automatons to transfinite working time. I know it has already been considered, but, as far as I can tell, GoL extended to ...
4
votes
1
answer
443
views
Necessity of omega-models in second order arithmetic
Are there examples of independence results over subsystems of true second order arithmetic that cannot be established using omega-models? To rule out trivial examples, let us assume that the base ...
1
vote
1
answer
264
views
How to select a subset of points from a universal to minimize the distance from outside to inside?
Here is the detailed problem.
I have a set of N points in K-dimension space, called U, and I want select M points of them, called S. For each point p in U, we define the distance from p to S as
$$ d(...
7
votes
2
answers
415
views
Only admissibles start gaps in clockable ordinals
This is a question about ITTM model introduced by Hamkins et al. In this paper it is proven that no admissible ordinal is clockable, so it either starts or lies within a gap in clockable ordinals. I ...
6
votes
2
answers
717
views
Let Abit$(x,y,n)$ be the $n$th bit of Ack$(x,y)$ (the Ackermann function). Is the function "Abit" primitive recursive?
Example of "Abit": Ack$(2,3)=9=1001_2$ (base 2). Thus Abit(2,3,3)=1
(the leftmost bit of $1001$. The index of the rightmost bit is 0)
Question 1: Is the function "Abit" primitive recursive (PR)?
...
9
votes
5
answers
2k
views
Are there natural, small, and total recursive functions that are not primitive recursive?
In a sense the Ackermann function is not primitive recursive (PR)
because it grows too fast.
Are there total recursive, not PR, small functions?
Using a diagonal argument,
we may define a total ...
28
votes
1
answer
2k
views
Why isn't this a computable description of the ordinal of ZF?
In a previous MO question, I was told by several commenters that
(a) it's known that there exists a computable ordinal $\alpha_{ZF}$ that "encodes the strength of ZF set theory" (i.e., a least ...
15
votes
1
answer
578
views
Computability of Brauer groups
A friend of mine and I were talking about computable algebra, and this question came up. The answer may already be known, but I couldn't find it with Google:
Suppose I have a countable field, $k$. ...
19
votes
3
answers
1k
views
Which distributions can you sample if you can sample a Gaussian?
Explicitly: You have a computer that is able to pick a real number at random according to the normal distribution: $\mathcal{N}(0,1) = \frac{1}{\sqrt{2\pi}}e^{-x^2/2}$. Which distributions can this ...
14
votes
2
answers
2k
views
Is this property equivalent to Lusin's property (N) for continuous functions?
A function $F:[0,1]\rightarrow\mathbb{R}$ satisfies Lusin's (N) property if for every measure zero set $A\subseteq [0,1]$, $F(A)$ has measure zero. (This includes the assertion that $F(A)$ is ...
26
votes
1
answer
3k
views
Is rule 30 Turing complete? Is there a proof that it isn't?
It is well known that the elementary cellular automaton known as rule 110 is Turing complete.
Its cousin rule 30 also produces complicated behaviour. When I read Wolfram's a New Kind of Science (in ...
1
vote
1
answer
612
views
relationship between corner tile and edge tile of wang tile
It is clear that any corner type of Wang Tile could be converted to edge type of Wang Tile by defining the edge color according to the corner color.
However, could we convert edge type of Wang Tile ...
2
votes
0
answers
158
views
Graph theoretical representation of Wang Tile
We note that for one dimensional tiling problem of Wang Tile could be represented by a graph. Each cycle on the graph represents a periodic solution.
However, is there a well established counter-part ...
3
votes
1
answer
503
views
Application of Combinatorics, Logic and computability theory in physical science: Tiling of Wang Tile with proportionality
The original problem of Domino Tiling and Wang Tile has great theoretical interest on computability theory... However, the great emerging problem on application of Wang Tile in material science and ...
3
votes
2
answers
285
views
Conjecture of a subset of Wang tile which might be decidable
From the two papers proving the undecidability of Wang tile in 1966 by Berger and in 1971 by RM Robinson, the tiles used in proving undecidability has a general common feature:
The left color and ...
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-...
5
votes
1
answer
630
views
Interaction between Turing and many-one reducibility
This is a question about two reducibility notions in computability theory. I suspect the answer is a fairly simple construction, and I'm just not seeing it.
For sets $X, Y\subseteq\omega$, we say $X$ ...
2
votes
2
answers
420
views
Absolutely algorithmically random infinite sequence
Let's call an infinite sequence of bits $f:N\rightarrow \{0,1\}$ absolutely random if any computably constructed subsequence is not computable, i.e. there aren't monotonic computable function $g:N \...
10
votes
2
answers
1k
views
What is the precise notion of "enough arithmetic" in Godel's first Incompleteness theorem?
I'm trying to reconstruct the proof of Godel's first theorem (Rosser's strong version) from the uncomputability of the Halting function. If we just started with the language $\mathcal{L}=\{0, S, +, \...
-1
votes
1
answer
417
views
What is the probability that a randomly chosen number from set of c.e.number is period(number)?
What is the probability that a randomly chosen number from the set of c.e.numbers is period(number)?
What is the probability that a randomly chosen number from the set of computable numbers is ...
3
votes
1
answer
357
views
What is the relation between KC and height of rational number?
Roughly speaking,Kolmogorov Complexity of a bits string or a description is the minimal length of programs outputing a bits string,and height of rational number is logarithm of the largest numerator ...
5
votes
6
answers
1k
views
practical algorithms for np complete problems
Inspired by:
Conjecture on NP-completeness of tesselation of Wang Tile up to finite size
And the practicality of this topic (solving tessellation on a lattice):
coloring in lattice
Computational ...
3
votes
1
answer
284
views
Decidability of prime gap sequences
Is the following problem undecidable?
Given a sequence of $n$ gaps $d_1,d_2,...,d_n$, does there exist a sequence of $n+1$ primes $p_1,p_2,...,p_{n+1}$ such that $p_{i+1} - p_i = d_i$ ?
If not, is ...
12
votes
0
answers
492
views
Do all linear orders in this class have computable copies?
This is a question which has been bothering me now for quite some time. I've talked to a number of people about it, and we've shown that a few basic ideas can't work, but other than that haven't made ...
6
votes
2
answers
706
views
Is every non-recursive set in $\Sigma_1$ complete in $\Sigma_1$ (relatively to many-to-one reductions)?
Most well known sets in $\Sigma_1 \setminus\Delta_0$, such as the
Halting problem, are complete in $\Sigma_1$, relatively to the
many-to-one reduction. In fact I don't know any example of a (non ...
2
votes
1
answer
581
views
Would a non-constructible set become constructible if we had oracles of arbitrarily high cardinality for the halting problems of ordinal computers?
I still have trouble to grasp the concept of a non-constructible set, my intuition is that we could "avoid" the non-constructibility of many of them if we assume we have "ordinal computers" extended ...
5
votes
1
answer
221
views
Attribution of an equivalence of the existence of omega-models of RCA0
There are many well-known equivalences in reverse mathematics between statements of the form "Every set is contained a countable coded $\omega$-model of $T$" and $S$, where $S, T$ are subsystems of ...
9
votes
3
answers
2k
views
What set theoretical questions could never be answered by Turing machines of arbitrary cardinality?
Let us assume that there are Turing machines of arbitrary cardinality, by that I mean they can have input tapes of any arbitrarily high cardinality and compute for a number of steps also of ...
6
votes
2
answers
489
views
What is the name of this type of groups?
Suppose $A$ is a finite set and $\Sigma=A\cup A^{-1}$. Let $L\subseteq \Sigma^{\ast}$ be a regular language on the alphabet $\Sigma$. Is there a common name for the group $G$ presented as:
$$G=\langle ...
2
votes
2
answers
613
views
Every infinite c.e.language is infinite or finite union of regular languages including at least one infinite regular language?
Is Every infinite c.e.language infinite or finite union of regular languages including at least one infinite regular language?
And is every infinite c.e.language that is not indexed language(that may ...
9
votes
3
answers
808
views
Conjecture on NP-completeness of tesselation of Wang Tile up to finite size
Motivated by these following questions on tessellation:
coloring in lattice
Reference for Wang Tile
Computational approach deciding whether a set of Wang Tile could tile the space up to some size
...
10
votes
2
answers
2k
views
Is Turing degree actually useful in real life? [closed]
In theoretical computer science, we classify problems according to their Turing degree. Is there any practical application of this?
Edit: Given that we cannot explicitly and mechanically understand ...
9
votes
4
answers
922
views
Are there two computable binary trees such that each has a branch not computing any branch through the other?
It is a well-known elementary classical result in computability theory that there are computable infinite binary trees $T\subset 2^{<\omega}$ having no computable infinite branch. (One can build ...
4
votes
1
answer
389
views
N^2 and two counter machines
I asked this question on cstheory a few months ago, but I didn't receive an answer, so I'm posting it here to see if there are original ideas from the "math world" to solve it. The original question ...
5
votes
1
answer
387
views
Computational approach deciding whether a set of Wang Tile could tile the space up to some size
As an applied person, I'm facing one practical problem deciding whether a set of Wang tile could tile the plane periodically or aperiodically. Although both problems seem undecidable, but I'm on a ...
4
votes
1
answer
154
views
Self-similarity in the theory of computability
Let $M = w_0w_1... \in \{0,1\}^*$.
For any computable function $f$ define $M_f = w_{f(0)}w_{f(1)}...$
Let for any computable strictly increasing function $f$ there is continuous
computable mapping ...
5
votes
2
answers
502
views
Reverse Math of High Sets?
Is there a standard principle in reverse math that is known to be equivalent (over $RCA_0$) to the existence of a set of high (Turing) degree? I'm interested in the general case, but would be happy to ...
4
votes
0
answers
118
views
Stabilization of recursive approximation in $PA^-+I\Sigma_1^0$
Over any model M of $PA^-+I\Sigma_1^0$. Suppose $A\in [T]$ where $T$ is a $\Delta_2^0$-tree and $A$ is one isolated path. Further, $A$ is regular, i.e. $\forall n A\upharpoonright n$ has a code in $M$....
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.
...
6
votes
2
answers
2k
views
Are there proofs of Rice Theorem without using the undecidability of some problem?
Most proofs of Rice theorem seem to be based on the undecidability of
the halting problem. They are "reduction-based".
Are there "direct" elementary proofs, perhaps based on diagonalization?
I think ...
9
votes
0
answers
523
views
"Hard" separation results in reverse mathematics (or similar)
This is a fairly broad question. In particular, I specify 5 questions (Q1, Q2.1, Q2.2, Q3, Q4) which for me all fall under one umbrella. Since this is unreasonably broad, I'm really interested in an ...
101
votes
4
answers
5k
views
How feasible is it to prove Kazhdan's property (T) by a computer?
Recently, I have proved that Kazhdan's property (T) is theoretically provable
by computers (arXiv:1312.5431,
explained below), but I'm quite lame with computers and have
no idea what they actually can ...
6
votes
1
answer
278
views
Is 0' of PA degree relative to a non-low set?
Definitions:
A set $X$ is of PA degree relative to a set $Y$ if every infinite $Y$-computable binary tree has an infinite $X$-computable path.
A set $X$ is low if $X'$ is computable from $\emptyset'$....
2
votes
0
answers
120
views
What are natural examples of non-relativizable proofs? [duplicate]
As I understand it, a proof that P=NP or P≠NP would need to be non-relativizable (as in recursion theory oracles).
Virtually all proofs seem to be relativizable, though.
What are good examples of ...