𝔖 Bobbio Scriptorium
✦   LIBER   ✦

The shortest definition of a number in Peano arithmetic

✍ Scribed by Dev K. Roy

Publisher
John Wiley and Sons
Year
2003
Tongue
English
Weight
89 KB
Volume
49
Category
Article
ISSN
0044-3050

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

The shortest definition of a number by a first order formula with one free variable, where the notion of a formula defining a number extends a notion used by Boolos in a proof of the Incompleteness Theorem, is shown to be non computable. This is followed by an examination of the complexity of sets associated with this function.

πŸ“œ SIMILAR VOLUMES

Expanding the additive reduct of a model
Expanding the additive reduct of a model of Peano arithmetic
✍ Masahiko Murakami; Akito Tsuboi πŸ“‚ Article πŸ“… 2003 πŸ› John Wiley and Sons 🌐 English βš– 124 KB πŸ‘ 1 views

## Abstract Let __M__ be a model of first order Peano arithmetic (**PA**) and __I__ an initial segment of __M__ that is closed under multiplication. Let__M__~0~ be the {0, 1,+}‐reduct of__M__. We show that there is another model __N__ of **PA** that is also an expansion of __M__~0~ such that __a__

The number of shortest cycles and the ch
The number of shortest cycles and the chromatic uniqueness of a graph
✍ C. P. Teo; K. M. Koh πŸ“‚ Article πŸ“… 1992 πŸ› John Wiley and Sons 🌐 English βš– 403 KB πŸ‘ 2 views

## Abstract For a graph __G__, let __g__(__G__) and Οƒ~g~(__G__) denote, respectively, the girth of __G__ and the number of cycles of length __g__(__G__) in __G__. In this paper, we first obtain an upper bound for Οƒ~g~(__G__) and determine the structure of a 2‐connected graph __G__ when Οƒ~g~(__G__)

On the complexity of finding paths in a
On the complexity of finding paths in a two-dimensional domain I: Shortest paths
✍ Arthur W. Chou; Ker-I Ko πŸ“‚ Article πŸ“… 2004 πŸ› John Wiley and Sons 🌐 English βš– 342 KB πŸ‘ 1 views

## Abstract The computational complexity of finding a shortest path in a two‐dimensional domain is studied in the Turing machine‐based computational model and in the discrete complexity theory. This problem is studied with respect to two formulations of polynomial‐time computable two‐dimensional do