Mathematical Logic9

Before：终于和计算机相关了😭😭😭😭😭他真的，我哭死。好玩！但怀疑作业依然不会做。。。

Mathematical Logic 9 Decidability and Enumerability

可判定性 和 可枚举性

Desicion problems 判定问题

判断给定输入是否满足特定性质

i.e
设 A* 是有限字母表上的字符串集合
input : w
满足某种性质 : w $\in$ W $\subset$ A*

判定问题的特征函数定义为：
f = 1 （w $\in$ W）
f = 0 （otherwise）

Decidability 可判定性

Def:
P 是对于性质W的一个判定程序（decision procedure for W），如果：
对于每个输入w，P终会停机，且输出一些w’使得：

• 如果 w $\in$ W，则w’ 为空串
• 否则，w’不为空串

我们称 W 是可判定的，如果存在这样的一个P

Enumerability 可枚举性

Def:
设A 是一个字母表，且 W $\subset$ A*.我们称P 是 W 的一个枚举程序，如果：
（在没有任何输入的情况下）P输出了W 中的所有单词（以某种顺序且可能重复）

我们称 W 是可枚举的，如果存在这样的一个P

Lemma about Enumerability

Lemma 9

如果W存在这样的一个枚举程序，那么 W 就一定存在一个没有重复的枚举程序

Lemma 10

如果A 是有限的，那么A* 是可枚举的。

Decidability VS Enumerability

Thm 11

所有可判定的集合都是可枚举的。

Thm 12

设W $\subset$ A*. W 是可判定的当且仅当 W 和 A*\ W 是可枚举的。

Q4：Can computers find proofs？

Undecidability of FO

any computer program cannot decide whether an arbitrary input mathematical statement has a proof

Register Machine

基本模型：
有限个寄存器R0,…,Rm,每个都可以存储字母表A 上的字符串。

一个程序由有限条指令组成，每一条都被标记为L $\in$ N

Instruction Type

• L LET R_i = R_i + a_j
  It is to add aj at the end of the word in Ri.

• L LET R_i = R_i - a_j
  If the word w in Ri ends with aj, then delete this aj; otherwise leave w unchanged.

• L if Ri = - then L′ else L0 or L1 or · · · or Lr
  It is to jump to a new location according to the ending letter of the word in Ri.

• L PRINT
  It is to output the word in R0.

• L HALT
  It is to halt the program.

Register Program

A program P starts with w $\in$ A* if in the beginning of the execution of P we have R0 = w and all other Ri are empty.

R-Decidability

W is register-decidable, or R-decidable for short, if there is a register program which decides W.

R-Enumerability

W is register-enumerable, or R-enumerable for short, if there is a register program which enumerates W.

Proposition 15

设W $\subset$ A*. W 是R-decidable 当且仅当 W 和 A*\ W 是R-enumerable的。