Two universal 3-quantifier representations of recursively enumerable sets

Thumbnail Image

Date

Authors

Journal Title

Journal ISSN

Volume Title

Publisher

Abstract

Description

It is proved that all recursively enumerable sets of natural numbers can be represented by arithmetic formulas (of two kinds) with only 3 quantifiers.
This is English translation of a paper originally published in Russian; several misprints were corrected

Keywords

Logic, 03D25

Citation

URI

http://salesiana.dossiersoluciones.com/handle/123456789/154346

Consulte el texto completo en el siguiente enlace:

https://arxiv.org/abs/0802.1052
 http://arxiv.org/abs/0802.1052
 Teoriya Algorifmov i Matematicheskaya Logika (a collection of papers dedicated to A.A.Markov), Vychislitel'nyi Tsentr Akademii Nauk SSSR, Moscow, 1974, pages 112--123

Collections

arXiv