类型论与机器证明简介

《同伦类型论》书的扉页

上篇文章介绍了命题逻辑、一阶逻辑再到ZFC集合论,本文来看一种新的宣称想要取代集合论在数学中地位的新东西——类型论。事实上它已经广泛运用在机器证明当中,其中最著名的就是四色定理的证明了,同时它跟程序代码很类似。把类型论稍加改造成同伦类型论,它还能比集合论更加“直接”地处理拓扑学中的许多问题。

类型论的动机

“类型”这一概念广泛被用于编程语言中,具体来说用于编译前的类型检查,比如下面这段C语言代码

1
2
3
int i = 0;       // 定义整数变量i,并将其设为0
string j ="oma"; // 定义字符串变量j,并将其设为"oma"
int k = i * j; // 定义整数变量k,并将其设为 i * j

编译时会报错,因为这段程序声明i是整数类型的变量,而j是字符串类型的变量,它们无法相乘,或者说,乘法运算是一个接受两个数作为输入参数,输出返回一个数的函数,这里输入的i、j的类型显然与之不匹配。从上面的例子可以看出,类型检查其实就是编译器帮助我们检查代码有没有明显的低级错误导致执行一些像把数字与字符串相乘的这种无意义的命令。虽然检查一个表达式的类型也是机械化的(可定义成形式系统),但这似乎跟数学逻辑没有一点关系,它居然能用来构建公理化体系?yugu233做过一期视频《论码农与数学家的相似性【数学地图】》非常通俗形象地解释了类型跟证明之间的联系。

Read More

公理化集合论简介

// 注:本文仅为作者最近学习了解集合论的大致总结,若想深入了解强烈建议找本数理逻辑的教材系统学习,维基百科也不错。

大家知道,数学有别于其它学科最重要就是严谨,比如上篇文章介绍了超越无穷的序数与基数,稍不小心就容易出错误。随着数学理论与证明过程越来越复杂,数学家急需一种能机械化规范证明的系统,使得可方便机器对其验证。在计算机发明之前就有人提出了它——形式系统。本文将从简单的形式系统开始,介绍命题逻辑、一阶逻辑,皮亚诺算数系统直到ZFC集合论这一主流数学中出镜最多的形式系统。

抱着边做边学的目的,我还慢慢搓出了一个能在网页上运行的形式系统模拟器“Deductrium”,后来又把它改造成了游戏。Deductrium中证明“a → a”

Read More

四维世界(十):旋转动力学

太空中的贾尼别科夫效应

/// 注:本文虽然大篇幅讨论的虚构四维世界中的虚构的物理规律,但也对纯数学的单位四维2-向量的均匀随机分布规律进行了讨论。

内容概要

  • 四维贾尼别科夫效应
  • 有能量交换的多体旋转系统
  • 角动量的随机分布律
  • 四维刚体的的主轴定理

贾尼别科夫效应

一个前苏联的宇航员在太空中把弄一个T字形零件,他偶然发现让零件漂浮着快速旋转起来,零件的旋转方向却突然时不时在空中翻转,后来就以他的名字(Джанибеков)命名了这个贾尼别科夫效应(Dzhanibekov Effect)。

Read More

四维计算机图形学:旋转篇

这次来看看如何实现最基础的坐标变换——旋转,它是渲染建模动画等一切技术的基石。这篇文章相当于一篇关于旋转的算法综述,虽然不需要读者熟悉计算机图形学,但会对数学水平要求稍微高一些,本文主要是罗列陈述算法,因此内容略显枯燥,若读者仅想学习使用这些工具构建四维交互场景,请关注后续的Tesserxel4D场景开发教程。

一般使用旋量表示N维空间中的旋转。特别地,3维与4维的旋量代数可以用四元数表示

特色内容

  • 三维四元数旋转相关算法
  • “几何代数”与“四元数”版四维旋量算法对比
  • 各种“lookAt”旋转生成算法
  • 四维相机的常见交互控制方式

前置知识

Read More

四维计算机图形学:渲染篇

之前的文章中几乎都覆盖了目前常见的可视化四维方法:截面法、球极投影、等高面或颜色标注第四维、3D照片等,其中3D照片又分线框与体素云等展示法。这些方法想必多数读者也能理解,但如何利用计算机程序去展示它们却是一个不小的挑战。这里先介绍一些最基本的计算机图形学原理,然后深入讲解各种绘制复杂四维物体的方法。读者可以根据自己的知识水平选读。或许我后面可以开一个系列专题,专门讲解怎样一步步自己搭建一个四维图形引擎。

立体照片中的线框渲染与截面渲染,且线框用颜色标注深度,左右画面为裸眼3D

特色内容

  • 三维计算机图形学基础
  • 体素/截面四维图形渲染
    • Shadertoy在线四维路径追踪演示
    • 四面体法/胞腔复形法
    • 体素云渲染方法
  • 线框渲染遮挡剔除算法

    Read More

玩Tesserxel(三):火车、飞行模拟器教程


Tesserxel中的四维飞机与四维火车

这篇文章将介绍Tesserxel中的四维一维轨道火车(传统铁路+火车)、二维轨道火车(也叫汽火/火汽车)、无人机四维客机四个示例场景的操控玩耍教程。之前几期介绍的场景都是静止的,我们只是主动操作摄像机换着四维角度以及三维角度观察场景本身或三维照片。这篇文章侧重于怎样驾驶操纵这些四维的交通工具,特别是如何操纵四维客机起降。这几个场景对应的交通工具的设计细节与运行原理已经在之前文章中均有一些介绍,感兴趣的话可以看看:

提示:如果在玩耍过程中觉得左边的示例场景侧栏很碍事可以点击顶部的隐藏侧栏,再设置浏览器进入全屏模式来获得最佳体验。

Read More