Search Results
| Search type | Search syntax |
|---|---|
| Tags | [tag] |
| Exact | "words here" |
| Author |
user:1234 user:me (yours) |
| Score |
score:3 (3+) score:0 (none) |
| Answers |
answers:3 (3+) answers:0 (none) isaccepted:yes hasaccepted:no inquestion:1234 |
| Views | views:250 |
| Code | code:"if (foo != bar)" |
| Sections |
title:apples body:"apples oranges" |
| URL | url:"*.example.com" |
| Saves | in:saves |
| Status |
closed:yes duplicate:no migrated:no wiki:no |
| Types |
is:question is:answer |
| Exclude |
-[tag] -apples |
| For more details on advanced search visit our help page | |
Results tagged with computability-theory
Search options not deleted
user 8628
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.
4
votes
2
answers
467
views
Is the collection of primitive recursive functions a lower set in the poset of computable fu...
If $g:\mathbb{N}\to\mathbb{N}$ is primitive recursive and $f:\mathbb{N}\to\mathbb{N}$ is computable such that $f(n) \leq g(n)$ for all $n\in \mathbb{N}$, does this imply that $f$ is primitive recursiv …
- 48.9k
3
votes
1
answer
232
views
Computabillity of packing of spheres with different radii
This is a conceptually easier version of a box packing problem I stated earlier.
Let $n$ be a positive integer and let $r_1, \ldots, r_n$ be positive integers. We take $r_i$ to be the radius of a sph …
- 48.9k
2
votes
0
answers
199
views
Integers $n$ such that $n^d + (n+1)^d$ is never prime
Let us call an integer $n>0$ pure if for all integers $d>0$ we have that $n^d + (n+1)^d$ is not prime. Is the set of pure integers non-empty? Is it computable?
- 48.9k
-1
votes
1
answer
69
views
Computability of a relation connected to the discrete logarithm [closed]
Informally speaking, I was wondering whether the relation
$a^k \equiv b \text{ (mod } n)$ for some $k,n$
is computable. More formally: Let $\mathbb{N}$ denote the set of the positive integers a …
- 48.9k
2
votes
2
answers
267
views
Meta-incomputability
Is there a set $B$ about which it provably cannot be decided whether it is computable in $\mathsf{ZFC}$?
- 48.9k
1
vote
1
answer
623
views
Computability of prime difference function
Consider the following function $f: \omega\to \{0,1\}$:
Set $f(n) = 1$ if for all $k\in \omega$ there are prime numbers $p,q > k$ such that $n = p-q$, and
set $f(n) = 0$ otherwise.
(Trivially, if …
- 48.9k
4
votes
2
answers
277
views
Checking for finite fibers in hash functions
Let $\{0,1\}^{<\omega}$ denote the collection of finite binary sequences. By a hash function we mean a computable map $$h: \{0,1\}^{<\omega} \to \{0,1\}^n$$ for some fixed $n\in\omega$. Define $\text{ …
- 48.9k
5
votes
2
answers
554
views
Box stacking problem
Real world problem alert: I am moving from my house to another one, and the problem below arised when I tried to fit some little boxes of various shapes into a large box:
We are given a positive inte …
- 48.9k
2
votes
1
answer
162
views
Is this cycling problem computable?
We have a group of $n$ people who must make a journey of length $d$. They are to start together, and their goal is to arrive at the destination at same time. They have a single bicycle, which they rid …
- 48.9k
2
votes
1
answer
230
views
Set of integer matrices $A$ such that $(A^k)_{k\in\mathbb{N}}$ is eventually periodic
This is a more elegant version of the original version which can be found below; it is based on a suggestion by Peter Mueller.
Let $\mathbb{N}$ denote the set of positive integers and for $n\in\mathb …
- 48.9k
1
vote
1
answer
515
views
Possible finite periodicities of "Rule 150" in the infinite setting
"Rule 150" is a fascinating one-dimensional and simple cellular automaton giving raise to some quite chaotic behaviour. This is the starting point of this question.
Let $\{0,1\}^\mathbb{Z}$ denote the …
- 48.9k
0
votes
1
answer
151
views
Realizability of metric matrices
We call an $n\times n$-matrix ${\bf A}\in \text{Mat}(n\times n, \mathbb{R})$ a metric matrix if
${\bf A}_{ii} = 0$ for all $i\in \{1,\ldots,n\}$,
${\bf A}_{ij} = {\bf A}_{ji}$ for all $i,j \in \{1,\l …
- 48.9k
3
votes
1
answer
125
views
The sequence of the power chromatic numbers $(\chi(G^n))_{n\in\mathbb{N}}$
For any finite, simple, undirected graphs $G, H$ we denote by $G\times H$ their categorical product. For any graph $G$ we let $G^1 = G$ and for $n\geq 1$ we let $G^{n+1} = G \times G^n$.
It is easy to …
- 48.9k
2
votes
1
answer
241
views
"Rule 30" in the infinite setting
This question tries to get right what went wrong in an earlier question.
Let $\{0,1\}^\mathbb{Z}$ denote the set of all functions $x:\mathbb{Z}\to \{0,1\}$. Let $+$ denote addition modulo $2$ on $\{0, …
- 48.9k
5
votes
1
answer
423
views
Is the set of generalized Fermat triples computable?
Is $\;\big\{(a,b,c)\in\mathbb{N}^3: \big(\exists m,n,\ell \in (\mathbb{N}\setminus\{0,1,2\})\big): a^m + b^n= c^\ell\big\}\;$ computable?
- 48.9k