|
Zapiski Nauchnykh Seminarov LOMI, 1972, Volume 32, Pages 77–84
(Mi znsl2567)
|
|
|
|
This article is cited in 2 scientific papers (total in 2 papers)
Arithmetical representations of recursively enumerable sets with a small number of quantifiers
Yu. V. Matiyasevich
Abstract:
It is shown that every recursively enumerable set $M$ of positive integers can be represented in each of the following forms:
\begin{align}
a\in M&\Leftrightarrow\exists_p\exists_s\&_{i=1}^\pi\exists_v[A_i(a,p,s,v)>0],\notag\\
a\in M&\Leftrightarrow\exists_s\&_{i=1}^\pi\exists_p\exists_v[B_i(a,p,s,v)>0],\notag\\
a\in M&\Leftrightarrow\exists_t\forall y_{\leq t} \exists_v\exists_w[C(a,t,y,v,w)=0].\notag
\end{align}
Here $\pi$ is a particular integer, $A_i$, $B_i$, $C$ are polynomials with integer coefficients, $a$, $p$, $s$, $t$, $v$, $w$, $y$ ware variables for positive integers.
Citation:
Yu. V. Matiyasevich, “Arithmetical representations of recursively enumerable sets with a small number of quantifiers”, Studies in constructive mathematics and mathematical logic. Part V, Zap. Nauchn. Sem. LOMI, 32, "Nauka", Leningrad. Otdel., Leningrad, 1972, 77–84
Linking options:
https://www.mathnet.ru/eng/znsl2567 https://www.mathnet.ru/eng/znsl/v32/p77
|
Statistics & downloads: |
Abstract page: | 288 | Full-text PDF : | 93 |
|