Skip to main content
Article
What are the ultimate limits to computational techniques: Verifier theory and unverifiability
Faculty Scholarship
  • Roman V. Yampolskiy, University of Louisville
Document Type
Article
Publication Date
7-28-2017
Department
Computer Engineering and Computer Science
Disciplines
Abstract

Despite significant developments in proof theory, surprisingly little attention has been devoted to the concept of proof verifiers. In particular, the mathematical community may be interested in studying different types of proof verifiers (people, programs, oracles, communities, superintelligences) as mathematical objects. Such an effort could reveal their properties, their powers and limitations (particularly in human mathematicians), minimum and maximum complexity, as well as self-verification and self-reference issues. We propose an initial classification system for verifiers and provide some rudimentary analysis of solved and open problems in this important domain. Our main contribution is a formal introduction of the notion of unverifiability, for which the paper could serve as a general citation in domains of theorem proving, as well as software and AI verification.

DOI
10.1088/1402-4896/aa7ca8
ORCID
0000-0001-9637-1161
Citation Information

Roman V Yampolskiy 2017 Phys. Scr. 92 093001