丘奇-图灵论题

The Church-Turing Thesis：所有算法都可以由一台图灵机来执行

如果一个语言的计算能力和通用图灵机相当，它是图灵完全 (Turing-Complete) 的。

虽然图灵机的概念很简单，但这是现代编程语言所能拥有的最高计算能力。一个图灵完备系统意味着在这个系统中写程序能够找到解决方法（不保证运行时和内存）。

图灵机

Turing Machines (TMs)

基本概念

图灵机与有穷自动机相似，但它有无限大容量的存储且可以任意访问内部数据。

它用一个无限长的带子作为无限存储，它有一个读写头，能在带子上读、写和左右移动。图灵机开始运作时，带子上只有输入串，其他地方都是空的，如果需要保存信息，它可将这个信息写在带子上。

它是一种更加精确的通用计算机模型，能模拟实际计算机的所有计算行为。
图灵机也有不能解的问题，事实上，这些问题已经超出了计算理论的极限。

图灵机计算过程中，当前状态、当前带子内容和读写头当前位置组合在一起，称为图灵机的格局 (configuration)。

在输入上的起始格局 (start configuration) 是格局，表示机器处于起始状态，并且读写头处于带子的最左端位置。
出现在带子上的第一个空白符 (Blank symbol, B) 表示输入的结束。

如果一个语言能被某一图灵机识别，则它是图灵可识别的 (Turing-recognizable)。

一台图灵机在读取一个串后可能进入三种状态：接受、拒绝、循环，如果图灵机进入循环状态，那它将永不停机 (halt)。
假设有语言A，如果能设计出一台图灵机M，对于任意字符串ω，如果ω∈A，那么 M读取 ω 后会进入接受状态，那么 A 是一个图灵可识别语言。
注意这个定义对于 ωA 的情况没有做出限制，它有可能拒绝，也有可能循环。

如果一个语言能被某一图灵机判定，则它是图灵可判定的 (Turing-decidable)。

图灵可判定语言的要求更严格，它要求语言A能设计出一台图灵机M：如果ω∈A，M进入接受状态，否则 (ωA) 进入拒绝状态。
如果一个语言是图灵可判定的，总能设计出一台图灵机，能在有限步数内判定一个字符串是不是属于这个语言。对所有输入都停机的图灵机，它们永不循环，称这种机器为判定器 (decider)。
一个语言是可判定的，当且仅当它既是图灵可识别的，也是补图灵可识别的。

If and are T-recognizable then is decidable.

形式化定义

图灵机是一个7元组

：输入字母表 (the input alphabet not containing the blank symbol)

：带子字母表 (the tape alphabet containing the blank symbol)

(Left, right)

Can a Turing machine contain just a single state?
No, . So, a Turing machine contains at least two states.

图灵机格局

(CS355 & CS370 两门课程对格局的画法略有不同)

🧻

The configuration of a Turing Machine captures its current state, the current tape contents, and the current position of the machine's head on the tape. A configuration essentially provides a snapshot of the machine at a particular moment in its computation.

图灵机 的格局是 的成员

: the set of halting states; is the start state.

: the tape content to the left of the tape head

: the start of the tape（虽然带有左端，但它向右无限延伸。为防止机器把带头移出带左端，我们假定带的最左端总是用表示）
: a sequence (possibly empty) of symbols from the tape alphabet

: blank symbol

即除非当前正在扫描空格符，否则所有格局都用左端符开始并且永远不用空格符结束

are configurations.

are not configurations.

可以使用简化记号来描述带内容（包括带头位置），例如把 写为

Where underlined position indicates the head position.

图灵机记号

🧻

If and are Turing machines then we could combine them to have new TM.

we know that , then we can display the machine above as (simply , or even )

By we mean “any symbole except ”.

Example

：机器首先会在带上写入一个空白符号。

：使用机器向右扫描直到找到一个非空白符号，上标2表示这个操作会连续进行两次。换句话说，机器会连续向右移动两次，直到连续找到两个非空白符号。

：机器在当前位置上写入符号。

Based on the copy Turing machine, give the sequence of tape changes on input

多带图灵机

Multitape Turing machine

转移函数改为允许多个带子同时进行读、写和移动读写头，其形式为

k 是带子的个数，表达式为
: stationary / no shift （多个读写头，可以一个移动，一个停止）

输入 仅出现在第一条带子上，输出可以在机器停机时从最后一条带上读取。

用一个带子来表示多个带子

Multi-tape TM on a standard TM: Represent k tapes sequentially on one tape using separators #

S= “ 对于输入 :

S 在自己的带子上放入

此格式表示了的全部个带子的内容。

为了模拟多带机的一步移动，S在其带子上从标记左端点的第一个＃开始扫描，一直扫描到标记右端点的第个＃，其目的是确定虚拟读写头下的符号。然后 S 进行第二次扫描，并根据M的转移函数指示的运行方式更新带子。

任何时候，只要 S 将某个虚拟读写头向右移动到某个＃上面，就意味着M已将自己相应的读写头移动到了其所在的带子中的空白区域上，即以前没有读过的区域（新带子）。因此，S在这个带子方格上写下空白符，并将这个带子方格到最右端的各个带子方格中的内容都向右移动一格。然后再像之前一样继续模拟。

定理：每个多带图灵机等价于某一个单带图灵机。

推论：一个语言是图灵可识别的，当且仅当存在多带图灵机识别它。

例子

描述格局序列

Give the sequence of conﬁgurations that enters when started on the indicated input string:

1#1

左移指的是读写头的位置移动，不是在状态图违反箭头方向移回去。

构造图灵机

Give implementation-level descriptions of Turing machines that decide the following languages:

从左往右扫描整个带子，隔一个字符就 ✖️ 掉一个0

如果在第1步之后，带子上只剩下唯一的一个0，则接受

如果在第1步之后，带子上包含不止一个0

如果0的个数是奇数，则拒绝
否则读写头返回至带子的最左端，并重复第1步

On input string

Sweep left to right across the tape, crossing off every other 0.

If in stage 1 the tape contained a single 0, accept.

If in stage 1 the tape contained more than a single 0 and the number of 0s was odd, reject.

Return the head to the left-hand end of the tape.

Go to stage 1.

在＃两边对应的位置上来回移动。检查这些对应位置是否包含相同的符号，如不是，或者没有＃，则拒绝。为记录对应的符号，消去所有检查过的符号。

当＃左边的所有符号都被消去时，检查＃的右边是否还有符号，如果是，则拒绝，否则接受。

On input string

Zig-zag across the tape to corresponding positions on either side of the # symbol to check whether these positions contain the same symbol. If they do not, or if no # is found, reject. Cross off symbols as they are checked to keep track of which symbols correspond.

When all symbols to the left of the # have been crossed off, check for any remaining symbols to the right of the #. If any symbols remain, reject; otherwise, accept.

{w| w contains an equal number of 0s and 1s}

课本答案

“ On input string w:

Mark the first unmarked 0 by scanning the tape. If there are no unmarked 0, go to step 4. Else, move the head back to the front of the tape.

Mark the first unmarked 1 by scanning the tape. If there is no unmarked 1, then reject.

Place the head back to the front of the tape and repeat stage 1.

Place the head back to the front of the tape and check if any unmarked 0’s or 1’s remain by scanning the tape. If there are none, accept else it reject.”

个人版本

“ On input string w:

Scan the tape and find 0, then mark it.

Scan the tape and find 1, then mark it.

Repeat stage 1 and 2 in sequence until there is no 0 found

If there is still a unmarked 1, then reject.
Else, accept.