-1

我只能说逻辑一定包括图灵机中的乘法和除法逻辑。但实际上我无法找出确切的解决方案。

4

1 回答 1

2

好吧，如果只是任何旧 TM 都可以，那么这个很容易理解。

  1. 输入磁带是#(n)#
  2. 使用 TM 将其写入磁带：#(n):(2):(n)#
  3. 使用 TM 从两者之后的事物中减去 : 之间的任何内容：一遍又一遍，直到（1）您要删除的符号太少（不可整除）或（2）剩下的符号正好为零（可整除） . 在 (1) 的情况下继续，否则 - 在 (2) 的情况下 - 停止拒绝作为非质数。
  4. 使用 TM 将其写入磁带：#(n):(m+1):(n)#
  5. 用TM来检查第一个之前的东西：大于两者之间的东西：。如果是，继续执行步骤 3。否则，停止接受（因为原始输入不能被大于自身的数字整除）

获取所有描述的 TM，并构建一个单一的 TM，该 TM 包含各种状态下的所有行为。这是素数语言的 TM。

假设一元编码（即自然数n由字符串 11...1 表示，其中 1 重复n次），这里有一些关于制作单个 TM 的更多指针：

  1. 原始输入
  2. 输入后转到第一个空白并写一个:。然后，向右写1。然后，向右写另一个1。然后向右写另一个：。然后，从开头到结尾的第一个空白来回弹跳，复制输入的自然数的一元数字。为此，请将输入数字更新为其他符号，例如 A，以便记住已复制的数字。当第一个 : 的左边有一个 A 时，停止这个过程。然后，将所有 A 设置回 1。
  3. 来回弹跳，为最里面的部分中的每个 1 从最右边的部分删除一个 1，更新最里面的部分以使用 A 标记它们。一旦标记了最里面部分中的所有内容，将它们设置回 1，然后重复该过程，直到最右边部分中的 1 用完。
  4. 擦除第二个：以及它之后的所有内容；然后在末尾写一个 1，然后是一个 :，然后按照 2 中描述的 TM 进行操作。
  5. 在最左边和最里面的部分之间来回弹跳，在每个部分中进行标记。如果最里面的部分先用完符号，则数字小于输入数字；如果你同时用完，数字是相同的，这意味着输入的数字首先可以被自己整除，所以它是素数。
于 2018-12-12T13:49:42.847 回答