X

曜彤.手记

随记,关于互联网技术、产品与创业

吉 ICP 备10004938-2号

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

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

第 5 章 - 终极机器

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

- 一个例子

  1. Page 136 非确定型图灵机(NTM):
  • 不确定性:每个“状态”和“纸带下字符”的组合,会允许多于一个的规则;
  • NTM 不会比 DTM 拥有更多的能力
  • *通过升级图灵机规范(随机内部存储、子例程、多纸带、多维纸带)以使其更强大的任何尝试都注定失败;
    • 使用“多状态”可以代替“随机内部存储”;
    • 可以直接扩张机器的规模来实现任意大小和复杂度的图灵机,无需任何对“子例程”的明确支持;
    • “多纸带”和“多维纸带”不会为图灵机增加额外的能力。
  1. Page 142 通用机器(UTM):
  • 相当于“其他机器的规则手册解释器”;
  • 读取一个 DFA 的设计(规则、起始状态以及接受状态),然后遍历 DFA 执行的每一步,同时使用另一部分纸带跟踪模拟机器的当前状态和剩余的输入(读取设计 -> 做事情);

第 6 章 - 从零开始编程

  1. 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 章 - 通用性无处不在

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

  1. Page 193 lambda 演算:可以模拟包括“通用图灵机”在内的任何图灵机(图灵完备);
  2. Page 196 部分递归函数
  • 由四个部分组成:
    • 零;
    • 递增;
    • 递归;
    • 最小化。

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

第 8 章 - 不可能的程序

  1. Page 236 计算机的实际目的是“执行算法”,但必须满足以下条件:
  • 有限:指令的数量是有限的;
  • 简单:指令要足够简单;
  • 终止:对于任何输入,一个遵守指令执行的人都会在有限步骤内终止;
  • 正确:对于任何输入,一个遵守指令执行的人都将得到正确的答案。
  1. Page 238 任何算法都能被一台机器(特别是一台 DTM)执行的思想叫作“邱奇-图灵”论题。
  2. 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
  1. Page 250 可判定问题:如果存在一个算法,对任何可能的输入都能保证在有限时间内解决一个判定性问题,那么这个问题就是“可判定(可计算)”的。
  2. 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
  • 程序行为为何难以预测?
    • 任何拥有足够能力引用自身的系统,都无法正确回答每一个关于自身的问题(哥德尔第一不完备定理);
    • 对于通用编程语言,不存在更强大的系统来解决第一个问题。
  1. Page 259 Rice 定理程序行为的任何“非平凡性质”都是不可判定的,因为停机问题总是能被规约成判定这个属性是否为 true 的问题;

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

(略)