数学代考| Computability 离散数学代写代写 - 代考代写：100%准时可靠您的作业代写专家

Alonzo Church (Fig. 13.3) developed the lambda calculus in the mid 1930 s, as part of his work into the foundations of mathemtics. Turing published a key paper on computability in 1936 , which introduced the theoretical machine known as the Turing machine. This machine is computationally equivalent to the lambda calculus, and is capable of performing any conceivable mathematical problem that has an algorithm.
Definition 13.4 (Algorithm)
An algorithm (or effective procedure) is a finite set of unambiguous instructions to perform a specific task.

A function is computable if there is an effective procedure or algorithm to compute $f$ for each value of its domain. The algorithm is finite in length and
$13.4$ Computability Fig. $13.3$ Alonzo Church
219
sufficiently detailed so that a person can execute the instructions in the algorithm. The execution of the algorithm will halt in a finite number of steps to produce the value of $f(x)$ for all $x$ in the domain of $f$. However, if $x$ is not in the domain of $f$ then the algorithm may produce an answer saying so, or it may get stuck, or it may run forever never halting.

The Church-Turing Thesis that states that any computable function may be computed by a Turing machine. There is overwhelming evidence in support in support of this thesis, including the fact that alternative formalizations of computability in terms of lambda calculus, recursive function theory, and Post systems have all been shown to be equivalent to Turing machines.

A Turing machine (discussed previously in Chap. 7) consists of a head and a potentially infinite tape that is divided into cells. Each cell on the tape may be either blank or printed with a symbol from a finite alphabet of symbols. The input tape may initially be blank or have a finite number of cells containing symbols.

At any step, the head can read the contents of a frame. The head may erase a symbol on the tape, leave it unchanged, or replace it with another symbol. It may then move one position to the right, one position to the left, or not at all. If the frame is blank, the head can either leave the frame blank or print one of the symbols.
Turing believed that a human with finite equipment and with an unlimited supply of paper could do every calculation. The unlimited supply of paper is formalized in the Turing machine by a tape marked off in cells.

We gave a formal definition of a Turing machine as a 7-tuple $\mathrm{M}=(Q, \Gamma, b, \Sigma, \delta$, $q_{0}, F$ ) in Chap. 7. We noted that the Turing machine is a simple theoretical machine, but it is equivalent to an actual physical computer in the sense that they both compute exactly the same set of functions. A Turing machine is easier to analyze and prove things about than a real computer.

A Turing machine is essentially a finite state machine (FSM) with an unbounded tape. The machine may read from and write to the tape and the tape provides memory and acts as the store. The finite state machine is essentially the control unit of the machine, whereas the tape is a potentially infinite and unbounded store.

A real computer has a large but finite store, whereas the store in a Turing machine is potentially infinite. However, the store in a real computer may be extended with backing tapes and disks, and in a sense may be regarded as unbounded. The maximum amount of tape that may be read or written within $n$ steps is $n$.

A Turing machine has an associated set of rules that defines its behaviour. These rules are defined by the transition function that specify the actions that a machine will perform with respect to a particular input. The behaviour will depend on the current state of the machine and the contents of the tape.

A Turing machine may be programmed to solve any problem for which there is an algorithm. However, if the problem is unsolvable then the machine will either stop in a non-accepting state or compute forever. The solvability of a problem may not be determined beforehand, but, there is, of course, some answer (i.e. either the machine either halts or it computes forever).

Turing showed that there was no solution to the decision problem (Entscheidungsproblem posed by Hilbert. Hilbert believed that the truth or falsity of a mathematical problem may always be determined by a mechanical procedure, and he believed that first-order logic is decidable: i.e. there is a decision procedure to determine if an arbitrary formula is a theorem of the logical system.

Turing was skeptical on the decidability of first-order logic, and the Turing machine played a key role in refuting Hilbert’s claim of the decidability of first-order logic.

The question as to whether a given Turing machine halts or not can be formulated as a first-order statement. If a general decision procedure exists for first-order logic, then the statement of whether a given Turing machine halts or not is within the scope of the decision algorithm. However, Turing had already proved that the halting problem for Turing machines is not computable: i.e. it is not possible algorithmically to decide whether a given Turing machine will halt or not. Therefore, there is no general algorithm that can decide whether a given Turing machine halts. In other words, there is no general decision procedure for first-order logic. The only way to determine whether a statement is true or false is to try to solve it.

Turing also introduced the concept of a Universal Turing Machine, and this machine is able to simulate any other Turing machine. Turing’s results on computability were proved independently of Church’s lambda calculus equivalent results in computability. Turing’s studied at Priceton Univsersity in 1937 and 1938 and was awarded a PhD from the university in 1938 . His research supervisor was Alonzo Church. ${ }^{5}$

图论代考

可以对图灵机进行编程，以解决存在算法的任何问题。但是，如果问题无法解决，那么机器要么停止在不接受状态，要么永远计算。问题的可解决性可能无法事先确定，但当然有一些答案（即机器要么停止，要么永远计算）。

图灵证明了决策问题（Entscheidungsproblem）是由希尔伯特提出的。希尔伯特认为一个数学问题的真假可能总是由一个机械过程来确定的，他认为一阶逻辑是可判定的: 即有一个决定程序来确定是否仲裁

图灵机有一组相关的规则来定义它的行为。这些规则由指定机器将针对特定输入执行的操作的转换函数定义。行为将取决于机器的当前状态和磁带的内容。

一台真正的计算机有一个大而有限的存储，而图灵机中的存储可能是无限的。但是，真实计算机中的存储可能会扩展为支持磁带和磁盘，并且在某种意义上可以认为是无界的。在 $n$ 步内可以读取或写入的最大磁带量为 $n$。

图灵机本质上是具有无限磁带的有限状态机 (FSM)。机器可以读取和写入磁带，磁带提供内存并充当存储。有限状态机本质上是机器的控制单元，而磁带是潜在的无限无限存储。

我们在第 1 章给出了图灵机的正式定义为 7 元组 $\mathrm{M}=(Q, \Gamma, b, \Sigma, \delta$, $q_{0}, F$ ) . 7. 我们注意到图灵机是一个简单的理论机器，但它相当于一台实际的物理计算机，因为它们都计算完全相同的一组函数。图灵机比真正的计算机更容易分析和证明。

在任何步骤，头部都可以读取帧的内容。磁头可以擦除磁带上的一个符号，保持不变，或用另一个符号替换它。然后它可以向右移动一个位置，向左移动一个位置，或者根本不移动。如果框架是空白的，头部可以将框架留空或打印其中一个符号。
图灵认为，拥有有限设备和无限供应纸张的人可以进行所有计算。在图灵机中，纸的无限供应通过在单元格中标出的胶带形式化。

图灵机（之前在第 7 章中讨论过）由一个磁头和一个可能无限的磁带组成，磁带被分成多个单元。磁带上的每个单元格可能是空白的，也可能印有来自有限符号字母表的符号。输入磁带最初可能是空白的或包含有限数量的包含符号的单元格。

Church-Turing Thesis 指出任何可计算函数都可以由图灵机计算。有压倒性的证据支持这一论点，包括根据 lambda 演算、递归函数理论和 Post 系统的可计算性的替代形式化都已被证明与图灵机等价。

如果有一个有效的过程或算法来计算其域的每个值的 $f$，则该函数是可计算的。该算法的长度是有限的，
$13.4$ 可计算性图. $13.3$ Alonzo Church
219
足够详细，以便人们可以执行算法中的指令。该算法的执行将在有限的步数中停止，以在 $f$ 的域中为所有 $x$ 产生 $f(x)$ 的值。但是，如果 $x$ 不在 $f$ 的域中，那么算法可能会产生这样的答案，或者它可能会卡住，或者它可能永远运行而永不停止。

Alonzo Church（图 13.3）在 1930 年代中期开发了 lambda 微积分，作为他研究数学基础工作的一部分。图灵在 1936 年发表了一篇关于可计算性的关键论文，介绍了被称为图灵机的理论机器。这台机器在计算上等同于 lambda 演算，并且能够执行任何可以想象到的具有算法的数学问题。
定义 13.4（算法）
算法（或有效过程）是一组有限的明确指令执行特定任务。

数学代写| DISCRETE MATHEMATICS代考请认准UprivateTA™. UprivateTA™为您的留学生涯保驾护航。

Cryptosystem
A system that describes how to encrypt or decrypt messages
Plaintext
Message in its original form
Ciphertext
Message in its encrypted form
Cryptographer
Invents encryption algorithms
Cryptanalyst
Breaks encryption algorithms or implementations

编码理论代写

编码理论（英语：Coding theory）是研究编码的性质以及它们在具体应用中的性能的理论。编码用于数据压缩、加密、纠错，最近也用于网络编码中。不同学科（如信息论、电机工程学、数学、语言学以及计算机科学）都研究编码是为了设计出高效、可靠的数据传输方法。这通常需要去除冗余并校正（或检测）数据传输中的错误。

编码共分四类：^[1]