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

Turing introduced the theoretical Turing Machine in 1936 , and this abstract mathematical machine consists of a head and a potentially infinite tape that is divided into frames. Each frame 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 frames 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 left or not at all. If the frame is blank, the head can either leave the frame blank or print one of the symbols (Fig. 7.7).

Turing believed that a human with finite equipment and with an unlimited supply of paper to write on could do every calculation. The unlimited supply of paper is formalized in the Turing machine by a paper tape marked off in squares, and the tape is potentially infinite in both directions. The tape may be used for intermediate calculations as well as for input and output. The finite number of
Fig. 7.7 Turing machine
128
7 Automata Theory t the finite states of
configurations of the Turing machine was intended to represent the finite states of mind of a human calculator.
next state to move to and what should be written on the tape, and where to move the tape head.

Definition 7.2 (Turing Machine) A Turing machine $M=\left(Q, \Gamma, b, \Sigma, \delta, q_{0}, F\right)$ is a 7-tuple as defined formally in [1] as

$Q$ is a finite set of states.
$\Gamma$ is a finite set of the tape alphabet/symbols.
$b \in \Gamma$ is the blank symbol (This is the only symbol that is allowed to occur infinitely often on the tape during each step of the computation).
$\Sigma$ is the set of input symbols and is a subset of $\Gamma$ (i.e. $\Gamma=\Sigma \cup{b}$ ).
$\delta: Q \times \Gamma \rightarrow Q \times \Gamma \times{L, R}^{4}$ is the transition function. This is a partial function where $L$ is left shift and $R$ is right shift.
$q_{0} \in Q$ is the initial state.
$F \subseteq Q$ is the set of final or accepting states.
The Turing machine is a simple machine that is equivalent to an actual physical computer in the sense that it can compute exactly the same set of functions. It is much easier to analyze and prove things about than a real computer, but it is not suitable for programming and therefore does not provide a good basis for studying programming and programming languages.

Figure $7.8$ illustrates the behaviour when the machine is in state $q_{1}$ and the symbol under the tape head is $a$, where $b$ is written to the tape and the tape head moves to the left and the state changes to $q_{2}$.

A Turing machine is essentially a finite-state machine (FSM) with an unbounded tape. The tape is potentially infinite and unbounded, whereas real computers have a large but finite store. The machine may read from and write to the tape. The FSM is essentially the control unit of the machine, and the tape is essentially the store. However, the store in a real computer may be extended with backing tapes and disks, and in a sense may be regarded as unbounded. However, 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. Its actions are defined by the transition function. It may be programmed to solve any problem for which there is an algorithm. However, if the problem is unsolvable then

图灵在 1936 年引入了理论上的图灵机，这个抽象的数学机器由一个磁头和一个可能无限的磁带组成，该磁带被分成多个帧。每个帧可以是空白的，也可以是用有限的符号字母表中的一个符号打印的。输入磁带最初可能是空白的或具有有限数量的包含符号的帧。在任何一步，头部都可以读取一帧的内容；磁头可以擦除磁带上的一个符号，保持不变，或者将其替换掉，或者根本不替换。如果框架是空白的，头部可以将框架留空或打印其中一个符号（图 7.7）。

图灵相信一个拥有有限设备和无限供应纸张的人可以完成所有计算。在图灵机中，纸的无限供应通过以正方形标记的纸带正式化，并且纸带在两个方向上都可能是无限的。磁带可用于中间计算以及输入和输出。有限的数量
图 7.7 图灵机
128
7 自动机理论 t 的有限状态
图灵机的配置旨在代表人类计算器的有限心理状态。
下一个要移动到的状态，应该在磁带上写入什么，以及将磁带头移动到哪里。

定义 7.2（图灵机）图灵机 $M=\left(Q, \Gamma, b, \Sigma, \delta, q_{0}, F\right)$ 是 [1] 中正式定义的 7 元组作为

$Q$ 是一组有限状态。
$\Gamma$ 是磁带字母/符号的有限集合。
$b \in \Gamma$ 是空白符号（这是在计算的每个步骤中允许在磁带上无限频繁出现的唯一符号）。
$\Sigma$ 是输入符号的集合，是 $\Gamma$ 的子集（即 $\Gamma=\Sigma \cup{b}$ ）。
$\delta: Q \times \Gamma \rightarrow Q \times \Gamma \times{L, R}^{4}$是转换函数。这是一个偏函数，其中 $L$ 是左移，$R$ 是右移。
$q_{0} \in Q$ 是初始状态。
$F \subseteq Q$ 是最终或接受状态的集合。
图灵机是一个简单的机器，在它可以计算完全相同的一组函数的意义上相当于一台实际的物理计算机。它比真实的计算机更容易分析和证明事物，但它不适合编程，因此不能为学习编程和编程语言提供良好的基础。

图 $7.8$ 说明了当机器处于状态 $q_{1}$ 并且磁带头下的符号是 $a$ 时的行为，其中 $b$ 被写入磁带并且磁带头向左移动并且状态更改为 $q_{2}$。

图灵机本质上是具有无界磁带的有限状态机 (FSM)。磁带可能是无限的和无限的，而真正的计算机有一个大而有限的存储。机器可以读取和写入磁带。 FSM 本质上是机器的控制单元，磁带本质上是存储。但是，在真实计算机中的存储可以扩展为支持磁带和磁盘，并且在某种意义上可以被认为是无界的。但是，在 $n$ 步内可以读取或写入的最大磁带量是 $n$。

图灵机有一组相关的规则来定义它的行为。它的动作由转换函数定义。它可以被编程来解决任何有算法的问题。但是，如果问题无法解决，那么

图论代考

排列是给定数量的对象的排列，一次取其中的一些或全部。组合是对多个对象的选择，其中选择的顺序并不重要。排列和组合是根据第 1 章中定义的阶乘函数定义的。 4.
计数原理
(a) 假设一个操作有 $m$ 个可能的结果，而第二个操作有 $n$ 个可能的结果，那么执行第一个操作后执行第二个操作时可能结果的总数是 $m \times n$ (Product Rule )。
(b) 假设一个操作有 $m$ 个可能的结果，而第二个操作有 $n$ 个可能的结果，那么第一个操作或第二个操作的可能结果总数由 $m+n$ 给出（求和规则） .
示例（计数原理 $(a)$ ）
假设掷骰子，然后掷硬币。有多少种不同的结果，它们是什么？
解决方案
掷骰子有六种可能的结果，$1,2,3,4,5$ 或 6，掷硬币有两种可能的结果，$\mathrm{H}$ 或 $\mathrm{ T}$。因此，结果的总数由乘积规则确定为 $6 \times 2=12$。结果由下式给出
$(1, \mathrm{H}),(2, \mathrm{H}),(3, \mathrm{H}),(4, \mathrm{H}),(5, \mathrm{H}) ,(6, \mathrm{H}),(1, \mathrm{~T}),(2, \mathrm{~T}),(3, \mathrm{~T}),(4, \mathrm{ ~T}),(5, \mathrm{~T}),(6, \mathrm{~T})$
示例（计数原理$(b)）$
假设掷骰子，如果数字是偶数，则掷硬币，如果是奇数，则第二次掷骰子。有多少种不同的结果？
解决方案
第一个实验涉及两个实验，涉及偶数和抛硬币。有 3 种可能的结果导致偶数和 2 种来自抛硬币的结果。因此，第一个实验有 $3 \times 2=6$ 的结果。

第二个实验涉及掷骰子和进一步掷骰子的奇数。掷骰子有 3 种可能的结果，导致奇数和 6 种结果。因此，第二个实验有 $3\times 6=18$ 的结果。
5.7 排列组合
97
最后，第一个实验有 6 个结果，第二个实验有 18 个结果，因此根据求和规则，总共有 $6+18=24$ 个结果。
鸽巢原理
鸽巢原则规定，如果将 $n$ 个项目放入 $m$ 个容器（其中 $n>m$），那么至少一个容器必须包含多个项目（图 5.1）。
示例（鸽洞原理）
(a) 假设有一组 367 人，那么必须至少有两个人的生日相同。

这很清楚，因为一年有 365 天（闰年有 366 天），所以一年最多有 366 个可能的生日。团体人数为 367 人，因此必须至少有两个人的生日相同。
(b) 假设有 102 名学生参加了一次考试（考试的结果是 0 到 100 之间的分数）。然后，至少有两名学生获得相同的分数。
这很清楚，因为测试有 101 种可能的结果（因为学生可能达到的分数介于 0 和 100 之间），并且班上有 102 名学生和 101 种可能的测试结果，那么必须至少有两名学生获得相同的分数。

数学代写| 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]