# Tagged Questions

25 views

### Primitive-recursive functions and polynomial equations

I am looking for examples of primitive-recursive functions $f:\mathbb{N}\rightarrow\mathbb{N}$ that can not be written as a pair of polynomials, i.e. $$f(n) = m \Leftrightarrow P(n,m) = Q(n,m)$$ ...
139 views

### Subsets of all Diophantine's sets

Function $\mathbb{N}^k \to \mathbb{N}^m$ is computable $\Leftrightarrow$ graph of function is Diophantine. Consider some subset $S$ of computable functions (for example some Grzegorczyk's class or ...
46 views

### A diophantine program for a basic For Loop

By Matiyasevich, every computable function has a diophantine representation. I am wondering if there is a general way to represent a simple iterative for loop. Specifically: Let $f(x)$ be any ...
49 views

### A diophantine definition of the Kleene star

Let $f(x \, | \, y_1, \dots, y_n)$ be a Diophantine polynomial that generates the Diophantine set $F$. By Matiyasevich, the set $F^*$ (Kleene star of $F$) is also Diophantine. My question: how can ...
22 views

### Show how the Diophantine sets are closed under concatenation.

It follows easily from Matiyasevich's Theorem that the Diophantine sets are closed under concatenation. I am trying to figure out the mechanism by which they are closed under concatenation. In other ...
38 views

### Which diophantine polynomials generate these diophantine sets?

Via Matiyasevich's Theorem, it is easy to prove that the following sets are diophantine: $\{k\}$ $\{0, 1, \dots, k-1, k+1, k+2, \dots \}$ $\{0, 1, \dots, k\}$ $\{k+1, k+2, \dots\}$ Number 1 is ...
46 views