# Tagged Questions

**9**

votes

**1**answer

255 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 ...

**27**

votes

**3**answers

1k 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 ...

**23**

votes

**2**answers

913 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 ...

**13**

votes

**2**answers

631 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 ...

**6**

votes

**1**answer

411 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 ...

**13**

votes

**2**answers

871 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?