《计算的本质：深入剖析程序和计算机》读书笔记（第 5-9 章）

Created on 2021 / 01 / 03, 22:09:13#编程语言

书接上回，本文为第 5-9 章的笔记。

第 5 章 - 终极机器

Page 125确定型图灵机（DTM）：

PDA 的限制：
- 只能使用“栈顶”资源，对于栈顶字符之下的内容没有办法随机访问；
- 栈的先进后出属性也会引起信息存储和获取的问题；
- 没有像样的“输出”，只有接受与否。
图灵机：能访问一条无限长纸带（既做存储又做输入）的有限状态机；
- 机器在某一时刻可能有着不同的状态；
- 拥有一个“纸带头”，指向纸带的一个特定位置，并且只能在这个位置读取或写入字符。每一步计算之后，纸带头都可以向左或右移动一个方格。
一种灵活的 DTM 规则格式：
- 机器的当前状态；
- 必须出现在纸带头当前位置的字符；
- 机器的下一状态；
- 要写入纸带头当前位置的字符；
- 写入纸带之后纸带头的移动方向（左/右）。
DTM 的确定性：“当前状态”和“纸带头下读到的字符”两者组合对应唯一的规则；

- 一个例子：

Page 136非确定型图灵机（NTM）：

不确定性：每个“状态”和“纸带下字符”的组合，会允许多于一个的规则；
NTM 不会比 DTM 拥有更多的能力；
*通过升级图灵机规范（随机内部存储、子例程、多纸带、多维纸带）以使其更强大的任何尝试都注定失败；
- 使用“多状态”可以代替“随机内部存储”；
- 可以直接扩张机器的规模来实现任意大小和复杂度的图灵机，无需任何对“子例程”的明确支持；
- “多纸带”和“多维纸带”不会为图灵机增加额外的能力。

Page 142通用机器（UTM）：

相当于“其他机器的规则手册解释器”；
读取一个 DFA 的设计（规则、起始状态以及接受状态），然后遍历 DFA 执行的每一步，同时使用另一部分纸带跟踪模拟机器的当前状态和剩余的输入（读取设计 -> 做事情）；

第 6 章 - 从零开始编程

Page 150无类型 lambda 演算（untyped lambda calculus）：

“lambda 演算”是一种新的“编程语言”，它只有三种表达式：“变量”、“函数定义”，以及“函数调用”；
计算模型不一定看起来像机器（比如“图灵机”），它们可以看起来像编程语言；
邱奇（“lambda 演算”发明者）编码：将数据表示为纯代码的技术（邱奇数、邱奇布尔值、邱奇有序对）。

- 数字（邱奇数）：某个动作的重复。

# def to_integer(proc)
#   proc[ -> n { n + 1 }][0]
# end
ZERO = -> p { -> x { x } }
ONE = -> p { -> x { p[x] } }
TWO = -> p { -> x { p[p[x]] } }
THREE = -> p { -> x { p[p[p[x]]] } }

- 布尔值（邱奇布尔值）：两个值中选择其一。

# def to_boolean(proc)
#   proc[true][false]
# end
TRUE = -> x { -> y { x } }
FALSE = -> x { -> y { y } }

- 有序对（邱奇有序对）：存储两个值，并在之后根据需要再次提供。

PAIR = -> x { -> y { -> f { f[x][y] } } }
LEFT = -> p { p[-> x { -> y { x } } ] }
RIGHT = -> p { p[-> x { -> y { y } } ] }
my_pair = PAIR[THREE][FIVE]

- Y-组合子：用于计算（高阶）函数的不动点，使得 lambda 演算可以定义“匿名递归函数”。

Y = -> f { -> x { f[x[x]] }[-> x { f[x[x]] }] }

- Z-组合子：Y 组合子对于像 Ruby 这样严格语言的变化。

Z = -> f { -> x { f[-> y { x[x][y] }] }[-> x { f[-> y { x[x][y] }] }] }

第 7 章 - 通用性无处不在

（*以下这些系统都具有模拟图灵机的能力）

Page 193lambda 演算：可以模拟包括“通用图灵机”在内的任何图灵机（图灵完备）；
Page 196部分递归函数：

由四个部分组成：
- 零；
- 递增；
- 递归；
- 最小化。

（SKI 组合子演算、Iota、标签系统、循环标签系统、Conway、Wolfram 2,3 图灵机，等略）

第 8 章 - 不可能的程序

Page 236计算机的实际目的是“执行算法”，但必须满足以下条件：

有限：指令的数量是有限的；
简单：指令要足够简单；
终止：对于任何输入，一个遵守指令执行的人都会在有限步骤内终止；
正确：对于任何输入，一个遵守指令执行的人都将得到正确的答案。

Page 238任何算法都能被一台机器（特别是一台 DTM）执行的思想叫作“邱奇-图灵”论题。
Page 241任何强大到足以通用的系统（能对自身求值），都不可避免地允许我们构建永不停机一直循环的计算。

完全编程语言：被仔细设计以保证它们的程序一定总是能停机的语言（无法解释自身）；
部分编程语言：与上述相反的语言。

- 一个解释自身的例子：

# does_it_say_no.rb
require 'stringio'

def evaluate(program, input)
  old_stdin, old_stdout = $stdin, $stdout
  $stdin, $stdout = StringIO.new(input), (output = StringIO.new)
  begin
    eval program
  rescue Exception => e
    output.puts(e)
  ensure
    $stdin, $stdout = old_stdin, old_stdout
  end
  output.string
end
def evaluate_on_itself(program) 
  evaluate(program, program)
end

program = $stdin.read
if evaluate_on_itself(program) == 'no' 
  print 'yes'
else
  print 'no'
end

ruby does_it_say_no.rb < does_it_say_no.rb

Page 250可判定问题：如果存在一个算法，对任何可能的输入都能保证在有限时间内解决一个判定性问题，那么这个问题就是“可判定（可计算）”的。
Page 251不可判定问题：

停机问题：对拥有一条特定纸带的特定图灵机，判定它的执行是否能够停机。（给定一个包含 Ruby 程序源代码的字符串，还有一个数据的字符串可以让程序从标准输入中读取，那么运行这个程序最终会得到一个答案作为结果，还是只会无限循环下去呢？）
- 如果停机问题可以判定，则“哥德巴赫猜想”便可以被证伪（写一个程序查找反例，并判定能否停机）。

- 不可避免的矛盾：

halts? 的分析结果与代码的实际运行结果是矛盾的（要么给出错误答案、要么陷入无限循环）；
可以类比为自然语言中的“说谎者悖论”，即：可否判断“我现在说的这句话是谎话”这句话的真假？

# do_the_opposite.rb
def halts?(program, input)
  # 解析程序；
  # 分析程序；
  # 如果程序在输入上停机，就返回 true，否则返回 false。
end
def halts_on_itself?(program)
  halts?(program, program)
end
program = $stdin.read
if halts_on_itself?(program)
  while true
    # 什么也不做；
  end
end

ruby do_the_opposite.rb < do_the_opposite.rb

程序行为为何难以预测？
- 任何拥有足够能力引用自身的系统，都无法正确回答每一个关于自身的问题（哥德尔第一不完备定理）；
- 对于通用编程语言，不存在更强大的系统来解决第一个问题。

Page 259Rice 定理：程序行为的任何“非平凡性质”都是不可判定的，因为停机问题总是能被规约成判定这个属性是否为 true 的问题；

第 9 章 - 在“玩偶国”中编程

（略）

Last built on 2023 / 10 / 26, 11:37:10

曜彤.手记