# NP理论（1）：图灵机与丘奇－图灵论题 精选

“可计算性”这个概念具有计算能力的含义，在图灵机“模型”中，机器的计算性能力可以具体化为机器的时间或空间能力，这个时空能力大小就表现在图灵机的一个主要构造——“纸带”上。图灵机的纸带“无限长”，其意义是说，图灵机作为所有计算机的“模型”，只表达一般性的算法时空能力，不对每台计算机的运行时间和存储空间作具体性的规定；但是另一方面，作为一台具体机器，其存储器空间的大小或机器运行时间的长短就是“无限长纸带”的具体化，总是有限的，虽然如此，但是一定是可满足计算要求的，也就是说，一台机器只有在自己的存储空间和可接受的机器运行时间内以能得到确定的计算结果为条件，这台具体机器才是有意义的——effectively calculable。

1，Turing machine (https://en.wikipedia.org/wiki/Turing_machine)

The machine operates on an infinite memory tape divided into cells. The machine positions its head over a cell and "reads" the symbol there. Then per the symbol and its present place in a finite table of user-specified instructions the machine (i) writes a symbol (e.g. a digit or a letter from a finite alphabet) in the cell, then (ii) either moves the tape one cell left or right, then (iii) (as determined by the observed symbol and the machine's place in the table) either proceeds to a subsequent instruction or halts the computation.

Note that every part of the machine (i.e. its state, symbol-collections, and used tape at any given time) and its actions (such as printing, erasing and tape motion) is finite, discrete and distinguishable; it is the unlimited amount of tape and runtime that gives it an unbounded amount of storage space.

2，Church–Turing thesis (https://en.wikipedia.org/wiki/Church–Turing_thesis)

In computability theory, the Church–Turing thesis is a hypothesis about the nature of computable functions. It states that a function on the natural numbers is computable by a human being ignoring resource limitations if and only if it is computable by a Turing machine.

3，Computable functions (https://en.wikipedia.org/wiki/Computable_function)

According to the Church–Turing thesis, computable functions are exactly the functions that can be calculated using a mechanical calculation device given unlimited amounts of time and storage space. Equivalently, this thesis states that any function which has an algorithm is computable and vice versa. Note that an algorithm in this sense is understood to be a sequence of steps a person with “unlimited time and an infinite supply of pen and paper” could follow.

4，Halting problem （https://en.wikipedia.org/wiki/Halting_problem）

The problem is to determine, given a program and an input to the program, whether the program will eventually halt when run with that input. In this abstract framework, there are no resource limitations on the amount of memory or time required for the program's execution; it can take arbitrarily long, and use arbitrarily as much storage space, before halting.

https://m.sciencenet.cn/blog-2322490-979317.html

## 全部精选博文导读

GMT+8, 2024-5-24 22:28