时间戳

首页 > 技术文章 > TCS学习笔记[0] 程序设计语言S 可计算函数

TCS学习笔记[0] 程序设计语言S 可计算函数

minor-second 2021-10-31 11:25 原文

目录

1 程序设计语言\(\mathscr S\)和可计算函数

1.1 预备知识

  1. Q: 本节考察的函数和一般数学书中的函数有什么异同？
    A: 把部分函数简称为函数（可能定义域中只有一部分有对应的函数值，其余无定义）
    注：处处无定义称为空函数。
    注：在本课程中，考虑的往往是\(N^n\to N(其中N=\{0,1,\cdots\})\)的数论函数，以及\((A^*)^n\to A^*\)的字函数。
  2. Q: 字符串的拼接运算对应什么代数结构？
    A: 封闭，有幺元\(\epsilon\)，有结合律，不可交换，没有逆元，则是幺半群。

1.2 Church-Turing论题

  1. Q: 如何理解“论题”？什么叫“推翻Church-Turing论题”？
    A: Church-Turing论题不是定理。它断言某个没有严格形式定义的直观概念（直观上的可计算性）对应于某个形式定义的数学概念。
    因此，Church-Turing论题更像是一个“定义”。“推翻”就是说该定义不合理，比如明显直观上可计算的按此定义不可计算，或者反之。
    注：由于\(\mathscr S\)语言特别简单，所以几乎很难从“直观上不可计算的按Church-Turing论题可计算”角度说Church-Turing论题不合理。
    思考：由于长时间的潜移默化，人们是否会认为计算机能算的就是直观可计算，从而使得Church-Turing论题永不会被推翻？

1.3 程序设计语言\(\mathscr S\)

  1. Q: 解释“无条件转向语句”。
    A: 设中间变量\(Z_i\)除了在此处不在任何地方出现，则
Z_i <- Z_i + 1
IF Z_i != 0 GOTO A_1

相当于无条件转向标号\(A_1\)，可以简记作GOTO A_1
GOTO A_1并不是\(\mathscr S\)的语句，但可以被宏展开成对应的\(\mathscr S\)程序片段。

  1. Q: 显然GOTO和IF V != 0 GOTO为基础可以构造出IF V = 0 GOTO的宏展开。那能否以IF V = 0 GOTO为基础（即：只能使用IF V = 0 GOTO，V <- V + 1，V <- V - 1三种语句）构造出另外两者呢？
    A: 显然IF Z_i = 0 GOTO A，其中Z_i是其它地方不出现的变量就是GOTO A的宏展开。
    而
    IF V = 0 GOTO B
    GOTO A
[B] V <- V + 1
    V <- V - 1

就是IF V != 0 GOTO A的宏展开。
（注：实际上在\(\mathscr S\)语言严格形式定义中，V <- V空语句也是允许的。这给宏展开带来了方便，且在之后还有其它理论上用途。）

  1. Q: 举例说明“一个宏展开和一个独立使用的程序是有区别的”
    A: 独立使用的程序初始时输入各变量值为0，且输出时任何副作用都可以被容忍，只需\(Y\)输出正确即可。
    但宏展开要考虑初始各变量的值，并避免副作用。
    例如赋值语句V <- V'，作为宏展开时，要考虑\(V\)初始取值未必为0. 并且在执行结束后V'的值不能受影响。
    具体地，初始时用一个“do...until循环”把V值减为0. 并使用
V' <- V' - 1
V <- V + 1
Z <- Z + 1

结构作“复制”（复制了两份V'），方便对V赋值完成后用副本Z把V'还原。

  1. Q: 解说上一问中出现的“do...until循环”说法，并用\(\mathscr S\)实现“while循环”。
    A:
[A] ...
    ...
    IF ... GOTO A

相当于do...until循环。当然截至目前IF处能填的条件只有简单的不等于0. 使用1.的宏的话也可以填等于0.
例如上一问中为了赋值V <- 0，采用如下do...until循环

[A] V <- V - 1
    IF V != 0 GOTO A

用\(\mathscr S\)语言实现while循环：

[A] IF ... GOTO B
    ...
    ...
    GOTO A
[B] V <- V

课本上为了不使用IF V = 0 GOTO的宏，写为了：

[A] IF ... GOTO B
    GOTO C
[B] ...
    ...
    GOTO A
[C] V <- V
  1. Q: 词义辨析：
    state 与 snapshot
    instruction 与 statement
    dummy statement 与 empty program 与 empty function
    A: 状态(state)是等式的有穷集合，对于每个程序中出现的变量存在唯一指定值。快相(snapshot)是二元组\((i,\sigma)\)，其中\(i\)是即将执行的指令编号。
    注：对于共\(q\)条指令的程序，编号从\(i=1\)到\(i=q\).
    初始时\(i=1\)，此时若\(\sigma\)是输入变量指定，其余变量为0的状态，则是初始快相。
    \(i=q+1\)表示计算结束，相应快相为终点快相。
    语句(statement)或者语句前加标号(label)是指令(instruction)，程序是有穷的指令序列（而不是语句序列）。
    空语句(dummy statement)V <- V不起任何作用，空程序(empty program)长度为0不含任何指令。空程序和只有空语句的程序效果相同。空函数(empty function)对任何输入无定义（程序执行不终止）。空程序计算的是恒为0的函数而不是空函数。

1.4 可计算函数

  1. Q: 解释记号\(\phi_\mathscr P^{(n)}\). 解释\(f(\cdot)=\phi_\mathscr P^{(n)}(\cdot)\)中的等号。
    A: 对于输入\(m\)元的程序\(\mathscr P\)，如果\(m>n\)则多余输入位补0，\(m<n\)删除多余输入，由此构造出\(n\)元数论函数，记为\(\phi_\mathscr P^{(n)}\).
    如果\(f\)和\(\phi_\mathscr P^{(n)}\)要么同时有定义且函数值相等，要么同时无定义（程序\(\mathscr P\)不终止），则称为部分可计算。全函数部分可计算则可计算。
  2. Q: 根据一般的程序设计语言中常见的运算符列举一些可计算函数（或谓词）。
    A: （合理即可）\(+,\dot -\)（特别注意此处加点，区分于部分函数\(-\)），\(\cdot,=,\ge,\le,\ne,<,>\)等等。

1.5 宏指令

  1. Q: 本节意在考察两种形式的宏指令：一般形式的赋值语句（）和一般形式的（）。
    A: W <- f(V_1, V_2, ..., V_n)，条件转移语句IF P(V_1, V_2, ..., V_n) GOTO L.
  2. Q: 对于一般形式赋值语句的宏展开，相比直接计算函数值的程序来说有什么改动？
    A: 改变原程序的\(\mathscr P\)的变量名，全部使用中间变量作输入输出，最后把中间变量\(Z_m\)赋值给\(W\).
    所有变量需要每次运行时先初始化为0.（因为宏展开中的语句可能执行多次）
    注：课本上只能看到部分初始化的语句，是因为有些初始化语句在更低层宏展开里。

推荐阅读