Formal System

什么是 逻辑形式系统(Foraml System)

• 一个可允许的字符的集合，我们可以用它来组成字符串（字符序列）

• 一个被称为 "公理 "的字符串的集合

• 一组规则，或称 "推理规则"，用于将一些字符串变为其他字符串

一个简单的例子

• (1) MI(公理)

• (2) MII(使用规则二)

• (3) MIIII(使用规则二)

• (4) MIIIIU(使用规则一)

• (5) MUIU(使用规则三)

• (6) MUIUUIU (使用规则二)

• (7) MUIIU (使用规则四)

模拟自然数乘法

• 规则一：给定一个字符串xtyqz，其中x,y,z是只由连字符组成的字符串，你可以组成x-tyqzy

• 规则二：给定一个字符串xtyqz，其中x,y,z是只由连字符组成的字符串，你可以组成xty-qzx

t ⇒ 乘以
q ⇒ 等于
- ⇒ 一
-- ⇒ 二

1. (1) -t-q- (公理)

2. (2) --t-q--(规则一)

3. (3) --t--q---- (规则二)

4. (4) --t---q------ (规则二)

t ⇒ 等于
q ⇒ 除以
- ⇒ 一
-- ⇒ 二

题目

1. 将字符串中的“0”替换为“11”，或者将字符串中的“1”替换为“00”；

2. 将字符串中的“000”或者“111”删除。

public void strCompare() {
    char[] s = "BBBAAAABA".toCharArray();
    char[] t = "BBBBA".toCharArray();
// 7,9,2,5
    // 7,9,1,4
int[] arr = {7, 9, 2, 5};
    int ls = s.length, lt = t.length;
    int[] ns = new int[10], nt = new int[10];
    ns[0] = nt[0] = 0;
// 
for (int i = 1; i < ls; i++) {
        ns[i] = ns[i-1] + ((s[i] == 'A') ? 1 : 0) * 2 - 1;
    }
    for (int i = 1; i < lt; i++) {
        nt[i] = nt[i-1] + ((t[i] == 'A') ? 1 : 0) * 2 - 1;
    }
    if (ns[arr[1]] - ns[arr[0]-1] - nt[arr[3]] + ns[arr[2]-1] % 3 == 0) {
System.out.println("no\n");
    } else {
System.out.println("yes\n");
    }
}

算法不是万能的

def bug(program):
	if checkhalt(program, program):
	  while 1:
	    pass
	  else:
	    return 1
// exec
bug(bug)