Two universal 3-quantifier representations of recursively enumerable sets

Simple item page
dc.creatorMatiyasevich, Yuri
dc.creatorRobinson, Julia
dc.date2008-02-07
dc.date.accessioned2026-07-07T09:19:19Z
dc.date.available2026-07-07T09:19:19Z
dc.descriptionIt is proved that all recursively enumerable sets of natural numbers can be represented by arithmetic formulas (of two kinds) with only 3 quantifiers.
dc.descriptionThis is English translation of a paper originally published in Russian; several misprints were corrected
dc.identifierhttps://arxiv.org/abs/0802.1052
dc.identifierhttp://arxiv.org/abs/0802.1052
dc.identifierTeoriya Algorifmov i Matematicheskaya Logika (a collection of papers dedicated to A.A.Markov), Vychislitel'nyi Tsentr Akademii Nauk SSSR, Moscow, 1974, pages 112--123
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/154346
dc.subjectLogic
dc.subject03D25
dc.titleTwo universal 3-quantifier representations of recursively enumerable sets
dc.typetext

Files

Collections

arXiv