问题标签 [turing-machines]

当我研究图灵机和 PDA 时，我认为第一个计算设备是图灵机。

因此，我认为存在一种叫做图灵机的实用机器，它的状态可以用一些特殊的设备（比如触发器）来表示，它可以接受磁带作为输入。

因此，我问了磁带中输入字符串是如何表示的，但是通过答案和我书中给出的细节，我开始知道图灵机在某种程度上是假设的。

我的问题是，如何实际实现图灵机？例如，它如何用于检查我们当前处理器中的拼写错误。

图灵机过时了吗？还是它们还在被使用？

我现在正在学习计算理论课程。我可以很好地理解这些概念。我能够解决问题。而且，当我向我的导师询问现实世界的应用程序时，他告诉我这些概念在编译器设计中肯定是有用且必不可少的。但是，至少要进行有意义的研究，我需要一些关于如何在我的编码中使用这些概念的解释。

例如，如果我想设计自己的 grep。我将在 C 中使用字符串函数。我不知道如何在编码中使用正则表达式。

同样的情况也适用于图灵机。

如果我想添加两个数字，为​​什么我必须使用那些一元概念。硬件是否实现了这些概念？

w^R 是 w 的倒数， w 是 {0, 1}* 。所以 TM 需要判断一个词后跟这个词的反义词后跟这个词。我不想要答案，我只想要一个开始并走上正轨的线索。

我想我接近这个答案，但仍然要确认我们是否可以创建一个可以进行实数计算并给出准确结果的图灵机（至少在原则上）？**例如找到整数的平方根。（其输出将是一个实数）我认为我们不能开发这种机器的逻辑是，实数是不可数无限的，对于不可数无限的语言，我们无法创建图灵机。

如何使用非确定性图灵机显示语言对上下文敏感？

我知道线性绑定自动机（LBA）接受的语言是上下文相关的语言。LBA 是一个非确定性的图灵机。

知道如何将所有这些联系起来并表明一种语言是上下文相关的吗？

通过练习测试为我的 cs 理论考试做准备。在问题中，我需要说明一种语言属于哪个“区域”（RL/DFSA/NFSA）/（CFG/CFL/NPDA）/（NP）/（EXPTIME）/（DL/DTM/NDTM）/（ TR），我意识到我不确定如何证明一种语言会超过（CFG/CFL/NPDA）区域。这里有 2 个问题（3 和 5），我知道它们不能在那个区域，因为它们会导致上下文无关语言的泵引理失败，我如何确定它们会属于哪个区域？

编辑：答案是 3 和 5 都属于 NP，但为什么呢？

例如，我知道语言

CFL 的泵引理不是上下文无关的，但我如何证明它属于 NP 而不是 exp。时间、可判定的语言还是可识别的图灵？

编辑：做了一些挖掘，我做的一个疏忽是 NP 中的问题是那些可以通过非确定性图灵机在多项式时间内验证的问题。我怎么知道：a：在多项式时间内存在该语言的验证器，并且 b：NDTM 可以识别它

我想这是一个关于图灵完备意味着什么的问题。awk 是一种编程语言，我听说你可以用这些语言做任何事情，但不是也有物理限制吗？我的意思是，你可能无法用我的世界红石电脑删除文件。同样，我想你不能用 AWK 做图形。

AWK 需要什么样的扩展才能进行图形处理？

如果这个问题是愚蠢的浪费时间，请给我投反对票（我只是不确定）。

谢谢！

我想编写一个程序来检查一个函数，比如 f 是否停止其输入的所有值。简而言之 -

例如在 JavaScript 中，

不需要 JS 中的解决方案，任何语言都可以。

谢谢。

我正在为这是否可以确定而苦苦挣扎：

A = {x 是自然数集的一个元素 | 对于每个大于 x 的 y，2y 是两个素数之和}

我倾向于认为这是可以决定的，因为当输入图灵机时，它永远不会达到接受状态并无限循环，除非它拒绝。但是，我也知道，要确定一种语言，必须只存在一种算法来确定它；我们不一定要知道它是如何完成的。有了这个，我的一部分认为它是可判定的？有人知道如何证明吗？