标签: computation-theory

如果您已经拥有算法的伪代码,它们是否有助于描述图灵机的功能？

我正在学习复杂性理论课程,我花了一些时间来描述一个决定或接受某种语言(状态,转换等)的图灵机器,即使我知道如何用C或甚至汇编这样的东西来编码它.我想我只是没有足够的图灵机练习(工作),但我很感激任何建议.

编辑

我不想制作图灵机模拟器,我想在纸上描述图灵机(字母,状态,过渡)来决定某种语言.

这是一个简单的例子,我的意思是,我需要编写一个超过0和1的字符串的图灵机,并将其中的所有0更改为1.例如,如果从磁带(输入)上的11010开始,它将在磁带(输出)上以11111停止.现在用高级语言,你知道它是这样的:

Go over every character on tape
    If character is 0 change it to 1

图灵机描述非正式地类似于:

你有两个状态,q和停止.当您处于状态q并且您看到1时,请在不更改的情况下向右转.如果看到0,则将其更改为1并向右移动.如果看到空白符号(磁带末尾),则转到暂停状态.

在形式上你会有类似{q,halt}的状态.{((q,1) - >(q,1,R)),((q,0) - >(q,1,R)),((q,#) - >(halt,0,L) )}用于过渡.

现在这个问题是微不足道的,但还有其他更多涉及(添加一元数或识别具有相同数量的a,b和c的语言).我可以轻松地为他们编写伪代码,但编写图灵机更具挑战性(需要我很长时间),我想知道是否有一些技巧,资源或指导方针可以帮助我更好地解决这类问题.

我知道上述定理的逆是不正确的,即如果L是规则的,那么L的每个子集都不需要是规则的

包含任意数量的带符号的图灵机M可以由仅包含三个带符号的一个M'模拟:{0,1,B}(B =空白).

M可以用只有两个磁带符号的M"模拟,比如{1,B}吗？

我已经研究了很多关于减少的问题,但我有一个不好的问题:我从CLRS中得到这个:

"......通过"减少"解决问题A来解决问题B,我们使用B的"容易度"来证明A的"容易度"."

我从"Christos H. Papadimitriou的计算复杂性"中得出这个结论:

"......如果B减少到A,问题A至少和问题B一样难."

我对这两个概念感到困惑:当我们使用easyiness时,我们说问题X简化为问题Y,如果我们有Y的多项式时间算法,并且还原过程是在多项式时间内完成的,那么问题X在多项式时间内是可解的,X是比Y容易或至少不比Y更难.

但是当我们使用硬度时,我们说问题X减少到问题Y并且Y比X更容易或者至少不比X更难.

我真的很困惑,请帮帮我.特别感谢.

如果我们主要使用无上下文语言进行编码,我真的无法理解如何模拟图灵机(它接受递归可枚举语言)的输出.

我有一个快速的问题。这里的上标加号是什么意思？

= {w ? {0,1} : w ? (0^+)(1^+)}

自从我完成这些以来已经有一段时间了。这是用于制作非确定性有限自动机

任务是在字母表 {0,1} 上构建该语言的 DFA。

我构建了一个由 4 个状态组成且不接受空字的 DFA。然而，在答案中，他们给出了接受它的 3 状态 DFA。

如果空词中奇数位置没有 1（这意味着它不在该语言中），为什么我的 DFA 应该接受空词？

给定两个向量,u=(ux,uy,uz)以及v=(vx,vy,vz),计算最便宜的检查它们是平行还是几乎平行的方法(给定一些近似阈值),假设向量没有标准化？

关于几乎平行:例如,我们假设一个阈值直到第一个小数部分,例如,如果它们的叉积是0.01我们可以安全地假设它们是平行的.我们可以类似地放宽我们可能想要使用的其他方法的条件.

如果首选遵循编程语言来回答,让我们假设我们想在c ++中这样做.

• 计算它们之间的角度是昂贵的,因为它需要使用反三角函数.
• 计算他们的交叉产品可能是一种方式,但不确定它是否是最有效的方式.
• 将它们标准化并验证它们的标量积是否为1.

如果存在xz = y,则X是字符串y的前缀,如果x不等于y,则x是正确的前缀.

只是想确保我正确理解这个概念.

例如,如果有一个字符串y ="abracadabra"是否意味着有大量可能的前缀？因此,如果x是前缀,则x可以等于"a","ab","abr"或甚至"abracadabra",但在这种情况下,当x = y时,它现在被称为不正确的前缀我认为.但是,我不确定x = y的最后一部分是否仍然可以被认为是前缀？

如果没有成员是另一个成员的正确前缀,则语言是无前缀的.

再次,不确定我是否正确理解它.例如,如果有一种语言="你好,世界!我的名字是安德鲁",我想,它是无前缀的,因为每个成员的开头都是彼此不同的.但是,如果我们有"你好,世界!你好吗？" 这种语言不再是无前缀的,因为"H"是"Hello"和"How"的前缀.我的思维方式是正确的还是我误解了什么？

我正在阅读的书中没有给出示例,这似乎是一个简单的话题,所以我想这可能是我找不到更详细解释的原因.但无论如何,我只是想确保我不会误解任何事情.

我会很感激所有的答案.谢谢.

为什么Forth实现了rot运算符,为什么它在堆栈的三个最顶层项目上运行？

这只是为了方便还是在没有这样的指示的情况下Forth不是Turing-complete？三个数量是图灵完成的最小可行选择吗？

我可以想象一个人可以rot用pick或实现roll.因此,如果这三个操作都没有,那么它仍然是图灵完成的吗？