Completeness of Hoare logic with inputs over the standard model
文献类型：期刊论文
| 作者 | Xu, ZW ; Sui, YF ; Zhang, WH |
| 刊名 | THEORETICAL COMPUTER SCIENCE
 |
| 出版日期 | 2016 |
| 卷号 | 612页码:23-28 |
| 关键词 | Hoare logic Peano arithmetic The standard model Computation Arithmetical definability Logical completeness |
| ISSN号 | 0304-3975 |
| 中文摘要 | 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 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. |
| 收录类别 | SCI |
| 语种 | 英语 |
| WOS记录号 | WOS:000369211200002 |
| 公开日期 | 2016-12-13 |
| 源URL | [http://ir.iscas.ac.cn/handle/311060/17412]  |
| 专题 | 软件研究所_软件所图书馆_期刊论文 |
| 推荐引用方式 GB/T 7714 | Xu, ZW,Sui, YF,Zhang, WH. Completeness of Hoare logic with inputs over the standard model[J]. THEORETICAL COMPUTER SCIENCE,2016,612:23-28. |
| APA | Xu, ZW,Sui, YF,&Zhang, WH.(2016).Completeness of Hoare logic with inputs over the standard model.THEORETICAL COMPUTER SCIENCE,612,23-28. |
| MLA | Xu, ZW,et al."Completeness of Hoare logic with inputs over the standard model".THEORETICAL COMPUTER SCIENCE 612(2016):23-28. |
入库方式： OAI收割
来源：软件研究所
浏览0
下载0
收藏0
其他版本
除非特别说明，本系统中所有内容都受版权保护，并保留所有权利。