问题标签 [decidable]

我需要证明 L 是否可判定：

L={<M> | M 是一个 TM，L(M) 和 H_TM 的并集在 RE}

（ H_TM={<M,w> | M 是一个在 w} 上停止的 TM）

我正在尝试定义以下数量部分：

但得到错误

由于 Hdecp，我如何帮助 Lean 认识到 (pi p) 确实是可判定的？

我是可判定性的新手。我读了停止问题的停止问题，但没有得到任何它实际上暗示的东西。我已经搞砸了解释。

谁能给我任何合理的解释或至少一些细节，这会有很大帮助吗？

根据所示段落，决策者 D 如何使用 H 作为子例程以及它的行为如何相反？

如果有人澄清这一点会非常有用吗？

这可能吗？假设我们有一个决策者决定 {|M 是一个 TM 并且 |L(M)|=n} 想要构建一个决策者决定 {|M 是一个 TM 并且 |L(M)|=n-1} 如果可能，如何？

我知道之前有人问过这个问题，但老实说，我并没有清楚地理解它。

我目前正在研究计算理论，我正在研究“证明一种语言是可判定的、可识别的或规则的”这样的术语。

用最简单的术语来说，它们实际上是什么意思，我们如何证明这些事情？

如果 L1 和 L2 是语言，我们就有了新的语言

例如，如果abc ∈ L1和123 ∈ L2，那么a1b2c3 ∈ INTERLACE(L1, L2)

我怎样才能证明INTERLACE是：

1. 可判定的？
2. 可识别？

我知道如何表明这种语言是有规律的。对于可确定的，我不太确定..

这是我的想法：

为了证明可判定语言的类在运算下是封闭的，INTERLACE需要证明如果A和B是两种可判定语言，那么有一种方法可以判断INTERLACE语言是否是可判定的。假设A,B可判定的语言 和M1,M2两个TM分别决定。

之后我想我不得不说如何构建识别语言的DFA？

Sipser 的 TOC 书中的定理 5.3 是关于 Regular_TM = {M | M 是图灵机 (TM)，L(M) 是常规语言}。为了达到矛盾，假设 TM R 是 Regular_TM 的决定者，然后 R 用于决定 Acceptance 问题，如打击 TM S 所示：

S = "On input (M,w) where M is a TM and w is a string: 1. Construct the code of TM M2 as follows: M2 = "On input x: (a) If x of the form 0^n1^n, accept. (b) else, run M on w and if M accepts w, then accept." 2. Run R on (M2). 3. If R accepts, accept; if R rejects, reject."

我有两个问题。第一个是 M_2 中的 x 固定吗？如果不是，它来自哪里？

第二个问题。为什么我们关心 M2 中的 x。如果 R 真的是一个决策者，我们为什么要关心检查 x 是否在 0^n1^n 中。那么下面的 TM S' 有效吗？

S = "On input (M,w) where M is a TM and w is a string: 1. Construct the code of TM M2 as follows: M2 = "On input x: //ignore x (a) run M on w and if M accepts w, then accept else reject." 2. Run R on (M2). 3. If R accepts, accept; if R rejects, reject."

我如何显示这种语言

是可判定的？

我相信如果我可以为 A 和 B 构建自动机，那么我可以得到一个包含它们的 shuffle 的自动机。

我也在考虑使用空性测试，但我还没有取得任何进展。

手头的问题如下：

令 S 是 N（自然数）的子集，因此它是无限且可数的。令 Ls={a^n | n 属于 S} 一种语言。Ls 是递归的吗？Ls 是递归可枚举的吗？证明你的答案。

我很确定 Ls 对于任何 S 都是递归的，因为我们可以编写一个决定 Ls 的程序（或就此而言的图灵机）。但是我该如何证明呢？