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.
34
votes
9
answers
5k
views
Decision problems for which it is unknown whether they are decidable
In computability theory, what are examples of decision problems of which it is not known whether they are decidable?
18
votes
0
answers
1k
views
Is the set of integers of the form $a/(b+c)+b/(a+c)+c/(a+b)$ computable?
The starting point of this question is the observation that the smallest positive integers $a,b,c$ satisfying
$$\frac{a}{b+c} + \frac{b}{a+c} + \frac{c}{a+b} = 4$$
are absurdly high, namely $$(1544768 …
- 48.9k
17
votes
1
answer
577
views
Aperiodic monotile in $\mathbb{R}$
Motivation. Recently a group of researchers found an aperiodic monotile in $\mathbb{R}^2$, answering a long-standing question. There are many results in higher dimensions, so let's explore the lower d …
- 48.9k
13
votes
0
answers
255
views
Is the set of power matrices decidable?
Let $\text{Mat}(n\times n,\mathbb{Z})$ denote the collection of integer $n\times n$ matrices. We say $M\in \text{Mat}(n\times n,\mathbb{Z})$ is a power matrix if there is an integer $k>1$ and a matrix …
- 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
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
4
votes
1
answer
160
views
Is sum-balanceability computable?
Let $\mathbb{N}$ denote the set of positive integers, and let $G=(V,E)$ be a finite simple, undirected graph. Given $f:V\to \mathbb{Z}$ we define the neighborhood
sum function $\mathrm{nsum}_f:V\to\ma …
- 48.9k
4
votes
0
answers
163
views
Tileability and computabilty
Let $n>2$ be an integer. We consider $n$ pairs $(x_1,y_1),\dotsc,(x_n,y_n)$ in $\mathbb{N}^2$, and the polygon defined by drawing a straight line from $(x_k, y_k)$ to $(x_{k+1},y_{k+1})$ and from $(x_ …
- 48.9k
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
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
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
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
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
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