Completeness of Hoare logic with inputs over the standard model

doi:10.1016/j.tcs.2015.08.004

	Completeness of Hoare logic with inputs over the standard model
	Xu, Zhaowei 1; Sui, Yuefei 2; Zhang, Wenhui 1
	2016-01-25
发表期刊	THEORETICAL COMPUTER SCIENCE
ISSN	0304-3975
卷号	612 页码:23-28
摘要	Hoare logic for the set of while-programs with the first-order logical language L and the first-order theory T subset of L is denoted by HL(T). Bergstra and Tucker have pointed out that the complete number theory Th(N) is the only extension T of Peano arithmetic PA for which HL(T) is logically complete. The completeness result is not satisfying, since it allows inputs to range over nonstandard models. The aim of this paper is to investigate under what circumstances HL(T) is logically complete when inputs range over the standard model N. PA(+) is defined by adding to PA all the unprovable Pi(1)-sentences that describe the nonterminating computations. It is shown that each computable function in N is uniformly Sigma(1)-definable in all models of PA(+), and that PA(+) is arithmetical. Finally, it is established, based on the reduction from HL(T) to T, that PA(+) is the minimal extension T of PA for which HL(T) is logically complete when inputs range over N. This completeness result has an advantage over Bergstra's and Tucker's one, in that PA(+) is arithmetical while Th(N) is not. (C) 2015 Elsevier B.V. All rights reserved.
关键词	Hoare logic Peano arithmetic The standard model Computation Arithmetical definability Logical completeness
DOI	10.1016/j.tcs.2015.08.004
收录类别	SCI
语种	英语
资助项目	973 Program of China[2014CB340701] ; National Natural Science Foundation of China[61272135] ; National Natural Science Foundation of China[61472474] ; CAS-SAFEA International Partnership Program for Creative Research Teams
WOS研究方向	Computer Science
WOS类目	Computer Science, Theory & Methods
WOS记录号	WOS:000369211200002
出版者	ELSEVIER SCIENCE BV
引用统计	被引频次：2[WOS] [WOS记录] [WOS相关记录]
文献类型	期刊论文
条目标识符	http://119.78.100.204/handle/2XEOYT63/8885
专题	中国科学院计算技术研究所期刊论文_英文
通讯作者	Xu, Zhaowei
作者单位	1.Chinese Acad Sci, Inst Software, State Key Lab Comp Sci, Beijing, Peoples R China 2.Chinese Acad Sci, Inst Comp Technol, Key Lab Intelligent Informat Proc, Beijing, Peoples R China
推荐引用方式 GB/T 7714	Xu, Zhaowei,Sui, Yuefei,Zhang, Wenhui. Completeness of Hoare logic with inputs over the standard model[J]. THEORETICAL COMPUTER SCIENCE,2016,612:23-28.
APA	Xu, Zhaowei,Sui, Yuefei,&Zhang, Wenhui.(2016).Completeness of Hoare logic with inputs over the standard model.THEORETICAL COMPUTER SCIENCE,612,23-28.
MLA	Xu, Zhaowei,et al."Completeness of Hoare logic with inputs over the standard model".THEORETICAL COMPUTER SCIENCE 612(2016):23-28.