标签: turing-machines

无论这是否可判,我都在苦苦挣扎:

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

我倾向于认为这是可判定的,因为当它被送入图灵机时,它将永远不会达到接受状态并且无限循环,除非它拒绝.但是,我也知道,对于一种可判定的语言,必须只有一种算法来决定它; 我们不一定要知道它是如何完成的.有了这个,我认为它是可判定的吗？有谁知道如何证明？

我正在用正式语言理论学习图灵机我的课程,教授建议运行以下算法来详细查看"TM"背后的逻辑,但是在尝试编译时不起作用告诉我以下错误.

C:\Documents and Settings\Melkhiah.EQUIPO01\Mis documentos\Downloads\Tarea3 Discretas\TM.c||In function `Tape* insert_tape(Tape*, Direction, char)':|
C:\Documents and Settings\Melkhiah.EQUIPO01\Mis documentos\Downloads\Tarea3 Discretas\TM.c|44|error: invalid conversion from `void*' to `Tape*'|
C:\Documents and Settings\Melkhiah.EQUIPO01\Mis documentos\Downloads\Tarea3 Discretas\TM.c||In function `Tape* create_tape(char*)':|
C:\Documents and Settings\Melkhiah.EQUIPO01\Mis documentos\Downloads\Tarea3 Discretas\TM.c|68|error: invalid conversion from `void*' to `Tape*'|
C:\Documents and Settings\Melkhiah.EQUIPO01\Mis documentos\Downloads\Tarea3 Discretas\TM.c||In function `Transition* get_transition(char*)':|
C:\Documents and Settings\Melkhiah.EQUIPO01\Mis documentos\Downloads\Tarea3 Discretas\TM.c|80|error: invalid conversion from `void*' to `Transition*'|
C:\Documents and Settings\Melkhiah.EQUIPO01\Mis documentos\Downloads\Tarea3 Discretas\TM.c||In function `List* insert_list(List*, char*)':|
C:\Documents and Settings\Melkhiah.EQUIPO01\Mis documentos\Downloads\Tarea3 Discretas\TM.c|93|error: invalid conversion from `void*' …

在所有图灵机扩展中(例如双向无限磁带,RAM,多个读/写磁头和非确定性),它们中的任何一个都允许TM来决定以前不可判断的问题吗？

据我所知，可以使图灵机执行在磁带上编码的指令的循环或迭代。这可以通过确定行分隔符并使Turing机器返回直到达到行分隔符的特定计数（即在循环内部）来完成。但是，图灵机还能执行递归程序吗？

有人可以描述这种图灵机的各种细节吗？

我想，如果可以通过图灵机执行递归，那么还可以执行Quicksort吗？

我是最后一年的工科学生.我和我的朋友们已经决定我们的最后一年项目是"使用模板元编程模拟图灵机".

我理解什么是"图灵机"和"模板元编程",但我的问题是,如果我们设计没有TMP的图灵机,模拟会很繁琐吗？如果我们使用TMP,我们可以获得哪些优势？如果我们不使用TMP但使用传统方法,我们会错过/获得什么？

关于我们将如何进行的任何建议？

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

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

我认为图灵机的时间复杂性和空间复杂性的辩护是相同的,我无法区分它们.

请帮我.谢谢.

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

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

如果这个问题是愚蠢的浪费时间(我只是不确定),请向我投票.

谢谢!

例如,如果我在输入的末尾并且我向左移动,我怎么知道我在磁带的最开头？如果有更多| _ | 在输入之前,我很容易再次告诉我,但我不知道是否有.这不是一个功课问题,我确信答案是显而易见的,这就是为什么我在网上找不到输入左边的磁带的原因.谢谢.

设计一个图灵机，输入两个非负数并对它们进行模运算，例如 mod(3,7)=3 和 mod(7,3)=1。显然，指定有关 TM 输入和输出的任何假设和格式。