Some Applications of Lawvere's Fixpoint Theorem

来源 :Research Articles | 被引量 : 0次 | 上传用户:555jl
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
The famous diagonal argument plays a prominent role in set theory as well as in the proof of undecidability results in computability theory and incompleteness results in metamathematics.Lawvere (1969) brings to light the common schema among them through a pretty neat fixpoint theorem which generalizes the diagonal argument behind Cantor's theorem and characterizes self-reference explicitly in category theory.Not until Yanofsky (2003) rephrases Lawvere's fixpoint theorem using sets and functions,Lawvere's work has been overlooked by logicians.This paper will continue Yanofsky's work,and show more applications of Lawvere's fixpoint theorem to demonstrate the ubiquity of the theorem.For example,this paper will use it to construct uncomputable real number,unnameable real number,partial recursive but not potentially recursive function,Berry paradox,and fast growing Busy Beaver function.Many interesting lambda fixpoint combinators can also be fitted into this schema.Both Curry's Y combinator and Turing's () combinator follow from Lawvere's theorem,as well as their call-by-value versions.At last,it can be shown that the lambda calculus version of the fixpoint lemma also fits Lawvere's schema.
其他文献
春雨、夏暑、秋霜、冬雪,我们从各种渠道获得的天气信息,都是风云卫星的功劳.然而,它的缔造者之一,我国著名卫星专家,我国静止气象卫星、雷达遥感卫星的开拓者,风云二号气象
期刊
平安养老险公司董事长兼CEO杜永茂指出,发达国家养老金积累主要是靠二三支柱的发展,推动总量的提升,而我国养老金储备严重不足主要差在二三支柱的缺失.
去行政化的治理变革诉求、准市场化的外部竞争压力以及全领域化的政策扩散逻辑驱动浙江省高校纷纷引入“最多跑一次”改革.各校改革的基本经验可以总结为整体性治理取向的改
WTO“中国原材料案”专家组对《中国入世议定书》第11.3条与《中国加入工作组报告》第170条的解释,存在着故意回避对关键用语的解释、不陈述理由以及“因果错位”等问题。上诉
中图分类号:D923 文献标识码:A DOI:10.19387/j.cnki.1009-0592.2019.12.240  现阶段,针对不动产交易安全以及市场经济稳定发展过程中,不动产物权变动模式起到了极为重要的作用。一般情况下,目前我国的不动产物权产生的变化便是《物权法》运用的登记生效模式和登记对抗多元变动模式,
从曹魏后期至东晋,郑玄、王肃之学的竞争构成这一时期经学史的一条重要线索,二者在礼制、经解等方面存在重要差异.而探讨王肃之学何以在郑学一统河洛的背景中兴起,特别是辨析
当前欧洲民粹政党在多国的兴起对欧洲主流政治发起了强有力的挑战.已有的解释民粹政党兴起的研究多为单因素解释,既不系统也不稳健,视角也较为静止.本文在理论反思的基础上,
随着韩国在国际上的影响力不断提升,中韩交流也日益频繁.近年来学习韩语或赴韩留学的学生数也呈增长趋势.虽然外国人学习韩语的目的多种多样,但最基本的目标可以说比较一致,
随着我国经济水平的发展,我国各领域均呈现出新的发展趋势,建筑规模及数量与日俱增,对城市化进程起到一定促进作用.市政道路桥梁施工作为建筑工程之一,对人们的出现带来一定
本文所要探讨的法学是一门关于法律适用之科学.法律的适用以行为和效果为其目的.法学以标准的、准确的法律规范为其研究对象;但这种规范性却是基于与规范性事实无关的各种方
期刊