Scroll Top
19th Ave New York, NY 95822, USA

数学代考| 离散数学代写

数学代写|Computability 离散代考

离散数学在计算领域有广泛的应用,例如密码学、编码理论、 形式方法, 语言理论, 可计算性, 人工智能, 理论 数据库和软件的可靠性。 离散数学的重点是理论和应用,而不是为了数学本身而研究数学。 一切算法的基础都是离散数学一切加密的理论基础都是离散数学

编程时候很多奇怪的小技巧(特别是所有和位计算相关的东西)核心也是离散数学

其他相关科目课程代写:组合学Combinatorics集合论Set Theory概率论Probability组合生物学Combinatorial Biology组合化学Combinatorial Chemistry组合数据分析Combinatorial Data Analysis

my-assignmentexpert愿做同学们坚强的后盾,助同学们顺利完成学业,同学们如果在学业上遇到任何问题,请联系my-assignmentexpert™,我们随时为您服务!

离散数学代写

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)。机器可以读取和写入磁带,磁带提供内存并充当存储。有限状态机本质上是机器的控制单元,而磁带是潜在的无限无限存储。

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

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

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

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

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

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

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

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

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

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

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

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

如果有一个有效的过程或算法来计算其域的每个值的 $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 离散数学

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

抽象代数代考

抽象代数就是一门概念繁杂的学科,我们最重要的一点我想并不是掌握多少例子。即便是数学工作者也不会刻意记住Jacobson环、正则环这类东西,重要的是你要知道这门学科的基本工具和基本手法,对概念理解了没有,而这一点不需要用例子来验证,只需要看看你的理解和后续概念是否相容即可

矩阵论代考matrix theory

数学,矩阵理论是一门研究矩阵数学上的应用的科目。矩阵理论本来是线性代数的一个小分支,但其后由于陆续在图论代数组合数学统计上得到应用,渐渐发展成为一门独立的学科。

密码学代考

密码学是研究编制密码和破译密码的技术科学。 研究密码变化的客观规律,应用于编制密码以保守通信秘密的,称为编码;应用于破译密码以获取通信情报的,称为破译,总称密码学。 电报最早是由美国的摩尔斯在1844年发明的,故也被叫做摩尔斯电码。

  • 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]

  1. 数据压缩(或信源编码
  2. 前向错误更正(或信道编码
  3. 加密编码
  4. 线路码

数据压缩和前向错误更正可以一起考虑

Related Posts

Leave a comment