X

曜彤.手记

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

吉 ICP 备10004938-2号

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


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

第 5 章 - 终极机器

  1. (Page:125)确定型图灵机(DTM):

- 一个例子

  1. (Page:136)非确定型图灵机(NTM):
  1. (Page:142)通用机器(UTM):

第 6 章 - 从零开始编程

  1. (Page:150)无类型 lambda 演算(untyped lambda calculus):

- 数字(邱奇数):某个动作的重复

# 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)不可判定问题

- 不可避免的矛盾

# 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 章 - 在“玩偶国”中编程

(略)



这是文章底线,下面是评论
  暂无评论,欢迎勾搭 :)