在进行考试修订时,我无法回答Sipser所着的"计算理论导论"一书中的以下问题.不幸的是,书中没有解决这个问题的方法.
解释为什么以下不是合法的图灵机.
M = {
输入是变量x1,...,xn上的多项式p
这真让我抓狂!我怀疑是因为整数集是无限的？这是否超出了字母表允许的大小？
我一直在努力寻找这个理论问题的答案,即使它不是一个直接的编程问题,我相信它确实是相关的.
假设一种不能超过1000个方格的图灵机.这种类型的可识别语言集与正常可识别语言集之间的关系是什么.
这是维基百科的可判定定义
在可计算性理论中,一个不可判定的问题包括一系列实例,其中需要特定的是/否答案,这样就没有计算机程序在给定任何问题实例作为输入的情况下,在有限数字后终止并输出所需答案.的步骤.更正式地说,一个不可判定的问题是一个语言不是递归集的问题
该递归集是的一个子集递归可枚举之一.在递归集之外有一些递归可枚举的语言.那么为什么递归上不可识别的语言不可判断？
我有一个家庭作业问题要求我描述一个接受的非确定性图灵机的程序L = {a^n: n is prime}.我不知道如何解决这个问题.我知道吗？我使用as作为一元数字并计算它们吗？我可以忽略字符串,只测试n的主要部分吗？或者是已知的主要值,因此只有那些单元格位置接受状态,我可以像正常一样读取数据？
我该怎么办呢？
在分析算法的时间复杂度时，我们通常认为数组的随机访问时间是一个常数（数组的大小n不是一个常数），但为什么呢？
考虑图灵机模型，其中数组存储在磁带中，要访问数组的特定元素，其磁带头必须移动到该位置，这需要 O(n) 时间。或者是否有其他方法来存储图灵机的数组，以便随机访问只需要恒定的时间？
图灵完整性是否会妨碍语言拥有 CFG？我找不到任何论文这么说。
grammar parsing turing-machines turing-complete context-free-grammar
如果您已经拥有算法的伪代码,它们是否有助于描述图灵机的功能？
我正在学习复杂性理论课程,我花了一些时间来描述一个决定或接受某种语言(状态,转换等)的图灵机器,即使我知道如何用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的语言).我可以轻松地为他们编写伪代码,但编写图灵机更具挑战性(需要我很长时间),我想知道是否有一些技巧,资源或指导方针可以帮助我更好地解决这类问题.
我碰巧需要一个用于图灵机的算法,该算法读取0的字符串,然后在磁带上写入二进制文件中有多少.
我意识到在实践中,机器实际上并不会计算0,但我很难知道如何做到这一点.
首先,我需要用X或其他东西来标记二进制数开始的位置,然后只为前0写一个1,如果最低有效位为0则为后面的每个0写一个它变为a 1但是如果它是1？也许把它变成0并继续左转将所有的1都变成0直到我找到0或空白变为1？然后再说一次,在这种情况下,无论LSB是什么都是一样的,因为我只做同样的事情,只有0才是第一个位置......
嗯......橡皮鸭......
在Michael Sipser的计算理论导论中,他指出:
"有些语言不具有可判定性,甚至图灵无法识别,因为有无数种语言,但只有相当多的图灵机.因为每个图灵机都能识别单一语言,而且语言比图灵机器多,有些语言无法识别任何图灵机"(178).
图灵机不是可以模拟任何计算机算法的假想机器吗？从理论上讲,您是否可以提出无数的算法？我无法绕过这个概念.我将非常感谢"像我5'这样的解释",但当然,任何帮助都比没有好.
我正在寻找图灵机暂停问题的简单解释.我知道TM的工作原理,它们如何枚举,机器配置等等,但我没有很好地处理暂停问题.
有人可以提供这个主题的好解释吗？