当前位置: 首页 > article >正文

LEAN 类型系统属性 之 算法式相等的非传递性(Algorithm equality is not transitive)注解

        由于 subsingleton 使用函数(eliminator) 的存在,导致算法式相等(Algorithm defintional equality)的非传递性。

在《定义上相等的非确定性(Undecidability of Definitional Equality)》 中有,

其中,定义上相等可替换规则起来作用:

同时,根据 归纳类型(Inductive Type)的简化规则(Reduction Rule),有:

简单来看是,intro 0 inv 0 a 的类型为 acc 0,而 inv 0 a 1 (p 0) 的类型为 acc 1,即两者的类型不同。由此,

实际上是,可达类型(Accessibility Type)中,

其使用规则定义的使用函数,是 subsingleton 使用函数(eliminator):

        这里,由于可达类型(Accessibility Type)的 subsingleton 使用函数(eliminator)在使用前值、前果时,由于前值与现值不属于同一类型,即 acc n 和 acc (n+1),因此,有,

        但是,f 0 a 没有使用规则(Elimination Rule)用于产生 f 1 (inv 0 a 1 ( p 0 ) ),也没有已经定义的简化规则可以使用,因此,

        在LEAN的设计上,算法式定义上相等是可确定的(Decidable),而定义上相等是不确定的(undecidable),由此,有些定义上相等的推演规则是没有对应的算法式定义上相等的规则,如 传递性(transitivity)只存在于定义上相等,也导致了其不确定性,即在判断定义上相等时,会陷入不能停止(non-terminated)。

        这里需要明确的是,LEAN系统内的所有能使用的转化规则,赋型规则等,都必须是LEAN显示(Explicit)定义的。


http://www.kler.cn/a/305500.html

相关文章:

  • 【云计算解决方案面试整理】1-2云计算基础概念及云计算技术原理
  • 【C++】new操作符的使用说明
  • MySQL Workbench导入数据比mysql命令行慢
  • 【C++】C++11特性(上)
  • 使用kalibr_calibration标定相机(realsense)和imu(h7min)
  • SciPy:Python 科学计算工具包的全面教程
  • Vue3+TypeScript二次封装axios
  • C++多态讲解
  • 进阶岛 任务3: LMDeploy 量化部署进阶实践
  • 在云服务器上安装配置 MySQL 并开启远程访问(详细教程)
  • JVM锁的优化与逃逸分析
  • CVE-2024-21096:MySQLDump提权漏洞分析
  • 基于深度学习的生物网络推理
  • 论文解读:利用大模型进行基于上下文的OCR校正
  • linux系统安装miniconda3
  • 云手机哪一款好用?手游专用云手机一览!VMOS云手机
  • Java学习Day41:骑龙救!(springMVC)
  • 在单片机中,处于高阻态是什么状态
  • GEE 教程:利用Google Dynamic数据进行逐月指定区域的土地分类数据提取分析
  • 【mysql】mysql之读写分离以及分库分表
  • Remote Connection Software,远程连接软件
  • 【Web】XGCTF 西瓜杯 超详细题解
  • 代码随想录:单调栈1-3
  • 浅谈人工智能之基于本地大模型的前后端平台开发示例
  • LINQ 和 LINQ扩展方法 (1)
  • OkHttp Interceptor日志上报