检索结果-内蒙古大学图书馆

Finitism, imperative programs and primitive recursion

JOURNAL OF LOGIC AND COMPUTATION 2021年第1期31卷 179-192页

作者： Leivant, Daniel Indiana Univ SICE Bloomington IN 47405 USA Univ Paris Diderot IRIF Paris France

Following the Crisis of Foundations Hilbert proposed to consider a finitistic form of arithmetic as mathematics' safe core. This approach to finitism has often admitted primitive recursive function definitions as obviously finitistic, but some have advocated the inclusion of additional variants of recurrence, while others argued that, to the contrary, primitive recursion exceeds finitism. In a landmark essay, William Tait contested the finitistic nature of these extensions, due to their impredicativity, and advocated identifying finitism with primitive recursive arithmetic, a stance often referred to as Tait's Thesis. However, a problem with Tait's argument is that the recurrence schema has itself impredicative and non-finitistic facets, starting with an explicit reference to the functions being defined, which are after all infinite objects. It is therefore desirable to buttress Tait's Thesis on grounds that avoid altogether any trace of concrete infinities or impredicativity. We propose here to do just that, building on the generic framework of [13]. We provide further evidence for Tait's Thesis by outlining a proof of a purely finitistic version of Parsons' theorem, whose intuitive gist is that finitistic reasoning is equivalent to finitistic computing.

关键词： Finitism primitive recursive arithmetic finite partial functions primitive recursive functions imperative programming loop variant Parsons' theorem

来源：评论

学校读者我要写书评

暂无评论

Finitism, Imperative Programs and Primitive Recursion

Finitism, Imperative Programs and Primitive Recursion

引用

International Symposium on Logical Foundations of Computer Science (LFCS)

作者： Leivant, Daniel Indiana Univ SICE Bloomington IN 47405 USA Univ Paris Diderot IRIF Paris France

ISBN: (纸本)9783030367558;9783030367541

The finitistic philosophy of mathematics, critical of referencing infinite totalities, has been associated from its inception with primitive recursion. That kinship was not initially substantiated, but is widely assumed, and is supported by Parson's Theorem, which may be construed as equating finitistic reasoning with finitistic computing. In support of identifying PR with finitism we build on the generic framework of [7] and articulate a finitistic theory of finite partialstructures, and a generic imperative programming language for modifying them, equally rooted in finitism. The theory is an abstract generalization of Primitive Recursive Arithmetic, and the programming language is a generic generalization of first-order recurrence (primitive recursion). We then prove an abstract form of Parson's Theorem that links the two.

关键词： Finitism Primitive recursive arithmetic finite partial functions Primitive recursive functions Imperative programming Loop variant Parson's theorem

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：