个人中心
文章发布
退出
作者热门文章
- html - 出于某种原因，IE8 对我的 Sass 文件中继承的 html5 CSS 不友好？
- JMeter 在响应断言中使用 span 标签的问题
- html - 在 :hover and :active? 上具有不同效果的 CSS 动画
- html - 相对于居中的 html 内容固定的 CSS 重复背景？
26
4
图灵机可以处理一些 LBA 无法处理的语言，但是有没有 LBA 无法解决但 TM 可以解决的有用的实际问题？
LBA 只是带有有限磁带的图灵机，而实际计算机的存储空间是有限的，因此在我看来，LBA 不能做任何具有实际重要性的事情。 除了 因为线性有界自动机不仅具有有限的带子，而且具有大小是输入大小的线性函数的带子。有限性的线性是否以某种方式限制了 LBA？
是否存在 LBA 无法解决但指数有界自动机可以(如果存在此类情况)的问题？
最佳答案
维基百科文章 context-sensitive languages指出任何递归
决策为 EXPSPACE 的语言(即可以被图灵机识别) -难的
不是上下文敏感的，因此不能被 LBA 识别。他们
举一个这样的语言的例子:包括幂运算的等价正则表达式对的集合。
关于theory - 与图灵机相比，线性有界自动机的有用限制是什么？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/2143204/
26
4
0
最近我试图向我的项目经理解释一些设计不佳的代码。所有的管理器类都是单例的(“这就是我不能轻易改变它的原因”)并且代码在任何一个函数调用就足够的地方使用事件分派(dispatch)(“这就是为什么它很难
我有一个简单的问题。这里的上标加号是什么意思？ = {w ∈ {0,1} : w ∈ (0^+)(1^+)} 我做这些已经有一段时间了。这是为了制作一个非确定性的有限自动机 最佳答案 0^+ 这意味着
就目前而言，这个问题不适合我们的问答形式。我们希望答案得到事实、引用或专业知识的支持，但这个问题可能会引起辩论、争论、投票或扩展讨论。如果您觉得这个问题可以改进并可能重新打开，visit the he
引用自 Algorithms for Java (sedgwick 2003) p。 135: “我们通常在开发或调试广告时使用驱动程序” 驱动程序是什么意思？ 谷歌只是给了我大量关于编程驱动程序的信
我坚信这样一种观点，即您从学习一门新语言中获得的最重要的东西之一不是如何使用一门新语言，而是您从中获得的概念知识。我不是问你认为 Assembly 有多重要或有用，我也不关心我是否从未在我的任何实
对于example，任何图灵机都不能接受不接受其自身编码的图灵机的语言。 最佳答案 TM不能决定无限多种语言。确实，“大多数”语言是不确定的。有许多可判定的语言，但有无数种语言(因此，无数许多不可判定
关闭。这个问题不符合Stack Overflow guidelines .它目前不接受答案。 想改进这个问题？将问题更新为 on-topic对于堆栈溢出。 5年前关闭。 Improve this qu
关闭。这个问题是off-topic .它目前不接受答案。 想改善这个问题吗？ Update the question所以它是 on-topic对于堆栈溢出。 8年前关闭。 Improve this q
我已经尝试证明这很有趣 bubble_main已订购，但似乎没有任何方法有效。这里有人能帮我证明引理is_ordered (bubble_main L)请。 我只是删除了我以前的所有引理，因为似乎没有
我目前正在研究离散数学测试，其中我们正在学习Chomsky's hierarchy和识别层次结构各个级别的自动机的类型。有人告诉我，大多数计算机语言都属于层次结构的“2级和1级”，但不完全属于该级别。
在我的编程类(class)原则中，我们谈论的是不同的调用方法。我们讨论了一些: 按值调用 通过引用进行调用 按值/结果调用 和调用，名称为 我找不到有关按名称调用的工作方式的示例。有人在乎给我举个例子
关闭。这个问题需要更多focused .它目前不接受答案。 想改善这个问题吗？更新问题，使其仅关注一个问题 editing this post . 3年前关闭。 Improve this questi
需要明确的是，我不是在寻找 NaN 或无穷大，也不是在问 x/0 的答案是什么。应该是。我要找的是这个: 根据硬件中的除法方式(我不知道它是如何进行的)，如果除以除数为0的除法，并且处理器在操作中愉快
关闭。这个问题需要details or clarity .它目前不接受答案。 想改善这个问题吗？通过 editing this post 添加详细信息并澄清问题. 4年前关闭。 Improve thi
我已经阅读了几页，包括 wiki 页面 http://en.wikipedia.org/wiki/Strong_and_weak_typing处理强类型语言和弱类型语言。在大多数情况下，我想我理解其中
停机问题对于图灵完备的语言是无法解决的，对于一些非 TC 语言，比如它总是停机的正则表达式，它可以很容易地解决。 我想知道是否有任何语言既可以停止也可以不停止，但承认一种可以确定它是否停止的算法。 最
好吧，我想这完全是主观的，但我在考虑随机数生成器的熵源。大多数生成器都是用当前时间播种的，对吗？好吧，我很好奇可以使用哪些其他来源来生成完全有效的随机(松散定义)数字。 使用多个来源(例如时间 + 当
我正在学习计算复杂性类(class)，到目前为止，我的印象是它对开发人员没有太大帮助。 我可能是错的，但如果你以前走这条路，你能举一个例子来说明复杂性理论如何帮助你的工作吗？万分感谢。 最佳答案 O(
在类里面，我们学习了停机问题，图灵机，归约等。很多同学说这些都是抽象无用的概念，了解它们没有任何意义(即，一旦类(class)结束就可以忘记它们)结束并且不会丢失任何东西)。 为什么理论有用？您是否曾
在多任务系统中，某些异常情况会阻止进程或线程的执行进度。我将进程和线程简称为“进程”。其中两种情况称为死锁和活锁。 前者指的是相互阻塞的进程，从而阻止其中一个进程执行。后者指的是相互阻止进程，但实际上
我是一名优秀的程序员,十分优秀！