-
0 votesanswersviews
在第一个符号左转的图灵机
我有一台图灵机，下表给出了转换 我正在输入字符串aaaa . 因此，如果我查看状态A中的第一个符号“a”，它表示用X替换它，进入状态B，然后向左移动 . 这是我困惑的地方 . 如果我正在查看第一个输入符号，怎么能向左移动？我只是去一个空白的符号？ 谢谢！ -
0 votesanswersviews
设计停止的图灵机
我被要求设计图灵机（使用状态和显式delta函数的oldschool方式） . 要求是：输入是TM应该停止的epsilon（无限数量的“空白”符号），使用的字母表是{B，0,1}（B是“空白”符号），以及最大状态数是5 . 目标是找到一个尽可能打印最大量“1”的解决方案 . 我的想法：首先打印两个“0”（我可以从2个状态中取出最大值），然后将每个0替换为“1”并将另一个“1”添加到字符串中 . 如... -
16 votesanswersviews
图灵机代码高尔夫
好的，今天's goal is to build a Turing machine simulator. For those that don'知道它是什么，见the Wikipedia article . 我们今天使用的状态表位于the Formal Definition that's part of that page的末尾 . 代码将采用一系列“0”和“1”字符串字符，一个表示机器开始的字符... -
3 votesanswersviews
设计图灵机的状态表
如果您已经拥有算法的伪代码，它们是否有助于描述图灵机的功能？ 我正在学习复杂性理论课程，我需要一段时间来描述一个决定或接受某种语言（状态，转换等）的图灵机器，即使我知道如何用C或甚至汇编这样的代码来编写它 . 我想我只是没有足够的图灵机练习（工作），但我很感激任何建议 . edit 我不想制作图灵机模拟器，我想在纸上描述图灵机（字母，状态，过渡）来决定某种语言 . 这是一个简单的例子，我的意思是，... -
2 votesanswersviews
图灵机 - 学习技巧
我花了整整一个月的时间来解决这个问题，因为我从练习书中得到了这个问题，我很想知道如何在图灵机上写这个 . 我真的很想学这个 . 请有人可以提供帮助吗？ 考虑登录的最后两个字母（如果两个字母相同，请选择拉丁字母中的下一个字母作为第二个符号） . 编写一个能识别语言Stretch（x 1）的图灵机 . 这是所有字符串的语言，包含两个字母的连续字符串，后跟'*'，后跟另一个字母串，每个字母x次出现，第... -
1 votesanswersviews
枚举器的图灵机图
我应该为语言0 ^ k1 ^ k（k> = 0）绘制一个枚举器 . 我不确定这与为这种语言构建图灵机状态图有什么不同：我理解它的方式是我需要通过模拟图灵来构建一个枚举器，该枚举器通过{0,1}以上的所有字符串识别上述语言在字符串i上为i步骤识别这种语言的机器，我无法想象如何使用状态图，但我的老师已经指出这是我们如何证明枚举器和图灵机器之间的等价，所以我认为我们要做的是使用为枚举器定义的转换函... -
8 votesanswersviews
请解释这个用Prolog编写的图灵机模拟器
Wikipedia Prolog article包括此图灵机模拟器： turing(Tape0, Tape) :- perform(q0, [], Ls, Tape0, Rs), reverse(Ls, Ls1), append(Ls1, Rs, Tape). perform(qf, Ls, Ls, Rs, Rs) :- !. perform(Q0, Ls0, Ls, R... -
-2 votesanswersviews
图灵机的数量？
你对这个问题有什么看法吗？我不知道它问的是什么 . 具有状态设置（Q-start，Q2，Q3，Q4，Q5，Q6，Q-accept，Q-reject），输入字母（0,1）和磁带字母（0）的图灵机数量是多少？ ，1，x，U）其中U是空白符号？启动，接受和拒绝状态是具有适当名称的状态 . 展示你的作品 . -
0 votesanswersviews
图灵机基本操作
在这个问题中，您需要构建几个图灵机 . 对于每个图灵机，提供其工作原理的高级描述并提供图形表示 . （如果图表完整，您可以省略正式定义 . ） a）编写一个图灵机T inc，它可以将1加到存储在图灵机磁带上的二进制编码数字上 . 二进制数用符号$括起来，你可以假设二进制数以0开头（即没有要考虑的溢出） . 例如，输入$ 0100 $由T inc转换为$ 0101 $，输入$ 0111 $由T i... -
0 votesanswersviews
图灵机擦除其输入
我有这个问题：考虑一个图灵机Cw，它擦除它的输入，在磁带上写w，并在扫描w的最左边的字符时停止 . 设计图灵机C011 我需要解释实际问题是什么以及Cw做了什么 . 我有点理解它在每个输入上都写出空符号，但其余部分对我来说都不清楚 . 希望有人能帮助我理解这个问题以及我需要做什么 . -
-1 votesanswersviews
任何人都可以给我关于图灵机设计的帮助
我遇到了一个基于基本图灵机的新算法非常棘手的情况 . 我知道图灵机的定义及其工作原理 . 但我真的不知道这个算法在说什么 . 有人可以帮我解决以下问题，还是给予任何可能的帮助？ 由图灵机执行的三阶段算法是非正式描述的 . 机器的输入字母是{a，＃}，磁带字母是{a，A，＃，B，＃，□}，它在磁带上的初始输入采用^ m＃a ^ n的形式，空白之后 . 准备阶段：从右扫描到第一个空白符号B并用□替换它... -
24 votesanswersviews
理论计算机科学什么时候有用？
在课堂上，我们了解了暂停问题，图灵机器，减少等等 . 许多同学都说这些都是抽象和无用的概念，而且知道它们并没有真正的意义（即，一旦课程结束，你就会忘记它们结束而不是失去任何东西） . 为什么理论有用？你有没有在日常编码中使用它？