All Questions
Tagged with computability-theory algorithms
19 questions
2
votes
0
answers
78
views
Is this variant of post correspondence problem undecidable?
The post correspondence problem, as defined by wikipedia, is undecidable. The problem is defined as follows.
Let $A$ be an alphabet with at least two symbols. The input of the problem consists of ...
- 21
1
vote
0
answers
216
views
How to solve special Diophantine equation systems (which one can solve by hand) with the computer?
I have a quadratic Diophantine equation system which is possibly not homogeneous and has some mixed and some linear terms.
But I know that there are only finitely many solutions over the integers.
One ...
- 1,755
13
votes
2
answers
1k
views
What is known in general about the liquid transfer problem?
In several puzzle books, I have seen the following kind of a problem: there are several containers that can hold up to certain amounts of liquid (these liquids are assumed to be infinitely divisible). ...
- 2,075
10
votes
2
answers
595
views
Transfinite algorithms
The Ford-Fulkerson algorithm is a classic algorithm that computes the maximum flow in a network. It is well-known that if irrational arc capacities are allowed, the algorithm does not necessarily ...
- 32.1k
3
votes
1
answer
239
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 ...
- 48.9k
5
votes
2
answers
581
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 ...
- 48.9k
4
votes
0
answers
164
views
Subgroup membership problem for Noetherian groups
I am interested in the status of the subgroup membership problem (MP) for finitely presented Noetherian groups. That is, given a finite presentation $\langle X,R\rangle$ for a Noetherian group,
\begin{...
- 343
8
votes
1
answer
351
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}((...
16
votes
1
answer
555
views
Computer software for periods
Kontsevich and Zagier define a period as an integral of a rational function (over $\mathbb{Q}$) defined on a $\mathbb{Q}$-semialgebraic set. They conjecture that if two periods are equal, then the ...
- 109k
28
votes
0
answers
907
views
On certain representations of algebraic numbers in terms of trigonometric functions
Let's say that a real number has a simple trigonometric representation, if it can be represented as a product of zero or more rational powers of positive integers and zero or more (positive or ...
- 6,819
1
vote
1
answer
280
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(...
- 573
10
votes
1
answer
582
views
Can Tarski decide constructibility in elementary geometry?
Can the decision routine for Tarski's Elementary geometry be extended to decide when an existence claim in that theory can be instantiated by a compass and straightedge construction?
The answer does ...
- 11.1k
33
votes
3
answers
6k
views
Are surjectivity and injectivity of polynomial functions from $\mathbb{Q}^n$ to $\mathbb{Q}$ algorithmically decidable?
Is there an algorithm which, given a polynomial $f \in \mathbb{Q}[x_1, \dots, x_n]$,
decides whether the mapping $f: \mathbb{Q}^n \rightarrow \mathbb{Q}$ is surjective,
respectively, injective? --
And ...
- 19.6k
2
votes
3
answers
445
views
Existence of equivalence checking algorithm
Set D : Set of decision algorithms
X∈D if and only if
X is a Turing machine algorithm with finite length
takes one input i, binary number
X(i)=0 or X(i)=1 or X(i) runs forever.
Definition: ...
- 123
30
votes
3
answers
3k
views
Is it decidable whether or not a collection of integer matrices generates a free group?
Suppose we have integer matrices $A_1,\ldots,A_n\in\operatorname{GL}(n,\mathbb Z)$. Define $\varphi:F_n\to\operatorname{GL}(n,\mathbb Z)$ by $x_i\mapsto A_i$. Is there an algorithm to decide whether ...
- 18.7k
13
votes
2
answers
832
views
Are the axioms for higher category-theory effectively computable?
I ask this, although I don't conduct any research in the area, or even plan to. -- There seems to be general agreement that the axioms for higher categories grow very rapidly in complexity as the ...
13
votes
6
answers
3k
views
Which model of computation is "the best"?
In 1937 Turing described a Turing machine. Since then many models of computation have been decribed in attempt to find a model which is like a real computer but still simple enough to design and ...
7
votes
1
answer
767
views
post correspondence problem variant
Is there an algorithm which takes as input two lists of words $v_1,...,v_n$ and $w_1,...,w_n$ over an alphabet $X$ and decides if there is an infinite sequence $(k_i)$ where $1 \leq k_i \leq n$ for ...
- 73
12
votes
2
answers
1k
views
What is the most compelling reason to believe Church's thesis? [closed]
Church's thesis states that the Turing machine is a universal model of computation. What is the most compelling argument supporting this assertion?
- 775