问题标签 [computability]

我试图围绕 lambda 演算，以及它与语言、编译器和二进制代码的关系。它实际上意味着什么 lambda 演算等同于图灵机，它实际上体现在哪里？

我不明白 lambda 演算如何取代图灵机作为计算的理论模型。图灵机是关于改变状态的顺序指令，lambda演算是关于表达式评估的东西。它更抽象，就像它自己的编程语言一样，而不是如何实际计算某些东西、让事情发生的模型。或者让我们这样说：λ演算就像路线图，而图灵机就像汽车模型。这两者如何被认为是等效的？是否可以在不实现图灵机的情况下在硬件上运行软件？

例如，lisp 编译器和语言如何与 lambda 演算相关？lambda演算在哪一层实现？就 lambda 演算的定义而言，实现是纯粹的吗？lambda 演算背后的理论在哪里以及如何将语法转换为运行的二进制文件？例如，在 lambda 演算中，数字被编码为特殊函数，应用于其他函数 n 次。然而在语法中，我们使用数字文字。所有这些公理都在哪里使用？

我必须证明语言 L = {< M >: |L(M)| <= 2016} 不是半可判定的。现在我想这样做：

取一个随机字母 E。现在 E 中有无限个单词。我们只能得出 |L(M)| <= 2016 通过将 E* 中的每个单词作为输入传递给 M。但是由于单词的数量是无限的，这意味着我们必须将输入传递给 M 无数次。但这意味着执行这些检查的图灵机最终会陷入无限循环，因此永远不会返回接受或拒绝它的输入。因此语言 L 不是半可判定的。

但我认为这可能不够正式？主要是因为我只是假设检查这种语言的图灵机会让 M 在 E* 中的每个单词上运行。这个假设是否有效，还是我应该更正式？

我对常规语言和上下文无关语言之间的区别有点困惑。递归语言是一种语言，其中存在一个总是停止的 TM。我在证明上述陈述时遇到了问题。

我想问一下减量。

在证明 Etm 在 M1 的定义中不可判定是

1.如果 x!=w，拒绝

2.如果 x==w，在输入 w 上运行 M，如果 M 执行，则接受

在我遇到的许多证明中，我看到了那条粗线，但我不明白我该怎么做，因为我不知道它是否会停止。

我会很高兴知道我错在哪里。

谢谢。

我们如何构建 TM 使其接受（仅提供描述）：

a + b = c

一个 。b = c

输入的格式为 a#b#c。

a,b 和 c 属于 {0,1}* 并且是正二进制无符号整数。

我知道如果输入具有一元表示，我们可以构造 TM，但是如果它具有二进制表示，如何解决？

给定语言 K = {e^hf^i | 2h > i > h} 我需要生成上下文无关文法

我想出的一些生产规则是：S -> eeTfff 和 T -> eTff | ε

它们仅在 n = m + 1 时起作用，但我不知道如何为 2h > i > h 中的每个组合生成任何规则。

令 T = {<M> | M 是一个 TM，只要它接受 w}，它就接受 wr ^。
证明 T 是不可判定的。

我对这个问题有两个答案——圣地亚哥：

5.9
令 T = { <M> | M 是一个 在接受 w } 时接受 w ^{r的 TM。}

假设 T 是可判定的，并让判定器 R 判定 T。通过如下构造 TM S从 A _TM减少：

• S：在输入 <M,w>
  1. 如下创建一个 TM Q：
     在输入 x 上：
     1. 如果 x 不具有 01 或 10 的形式，则拒绝。
     2. 如果 x 的形式为 01，则接受。
     3. 否则（x 的形式为 10），在 w 上运行 M，如果 M 接受 w，则接受。
  2. 运行 R
  3. 如果 R 接受，则接受，如果 R 拒绝，则拒绝。

因为 S 决定了 A _TM，它已知是不可判定的，所以我们知道 T 是不可判定的

未公开来源：

• 5.12我们通过将‹<em>M, w ›映射到‹<em>M'›来 证明A _TM ≤<sub>m S ，其中M'是以下TM：

  • M' = “在输入x上：
    1. 如果x = 01 则接受.
    2. 如果x ≠ 10 则拒绝。
    3. 如果x = 10在w上模拟M。 如果M接受w然后接受; 如果M停止并拒绝，则拒绝。”
       

  如果 ‹<em>M, w › ∈ A _TM那么M接受w并且L ( M' ) = {01,10}，所以 ‹<em>M'› ∈ S。
  相反，如果 ‹<em>M, w › ∉ A _TM则L ( M' ) = {01}，所以 ‹<em>M'› ∉ S。因此，
  ‹<em>M, w › ∈ A _TM ⇔ ‹<em>M'› ∈ S。

但我不明白以下内容：

1- x 和 w 之间的关系是什么？

2- 为什么我们考虑 ‹<em>M, w › ∈ A _TM和‹<em>M, w › ∉ A _TM这两种情况？

3-为什么如果 A 映射可简化为 S 这会使 S 不可判定？

谁能为我澄清这些观点？

无论乘法（或除法）运算如何实现（即是软件功能还是硬件指令），都无法及时求解O(1)。对于大n值，处理器甚至无法通过一条指令计算它。

在这样的算法中，为什么这些操作是恒定的而不依赖于n？

我试图证明语言 L = {w ∈ {0, 1} ∗ | 输入 x} 的 Mw(x) ↓ 部分可判定但不可判定。Mw 是 M 的编码，因此语言 L 使得机器 M 的所有编码在某个输入 x 上停止。

我有两个想法：

1. 使用一些决策者 TM 将其减少到停止问题
2. 使用 Post 定理并以某种方式证明 L 的补码是不可判定的，但 L 是部分可判定的

但是，我无法确定这两者中的哪一个实际上是正确的，以及如何用正确的符号来编写它。谁能提供一些提示？

在停机问题的证明中，为什么我们必须将机器及其描述作为输入传递？

例如，我可以通过机器的描述和其他一些输入（不是机器本身），但矛盾的证明仍然有效。

例如，假设 H(a, b) 如果 a 确实在“b”上停止，则给出答案“是”，否则给出“否”。

现在我们创建另一台机器“H*”，它的作用与 H 的作用相反。

H 停止意味着 H* 进入无限循环，而 H 不停止意味着 H* 停止。

现在不是通过 H(H*, H*); 如果我通过了 H(H*, X) 那么这意味着如果 H* 没有在 X 上停止，H* 将停止，反之亦然（它仍然是矛盾的证明）。

我不一定看到传递 H(H*, H*) 而不是仅仅传递 H(H*, X) 的想法。在后一种情况下，证明不工作吗？