turing-machines - 图灵可判定语言和图灵可判定机器。区别？

Question

我有一台图灵机 M，我已经证明 M 不是决策者。然后我证明了 A=L(M) 或 M 识别的语言 A。我现在被问到“语言（A）图灵可判定”。

我的问题是，如果我已经证明 M 不是决策者，我能不能用它来暗示语言 (A) 不是图灵可判定的？在我看来，机器 M 的语言不仅包括公认的语言，还包括永不停止的无限长字符串。那会使语言也不是图灵可判定的吗？

感谢您的任何建议。

Answer 1

I think there are some ambiguities in the question that should be clarified. To be in the same page, let me clarify some definitions:

Definitions

1. A formal language L is called "Turing-decidable" if there exists a "decider" for it.
2. A "decider" is a TM that halts on all strings of Sigma-star (Sigma is the alphabet of this TM.). To be specific, when we input strings from L (that should be accepted), or from L-bar (that should be rejected), the machine halts. Note that all of these strings are from Sigma-star. We are not allowed to input strings outside of Sigma-star.
3. “String” is a finite sequence of symbols from alphabet. Therefore, in your question: “... infinite long strings ...” is an invalid statement in formal languages because of strings must be finite.

So, when you say, you’ve proven M is not a decider, it means, you’ve proven that M falls in an infinite loop for “at least one string of Sigma-star”. This string can be in the set A or A-bar.

My point here is that you cannot prove a TM is, per se, decider or non-decider without any language.

Now, based on this clarification, if you got your answer, that’s excellent, but if not, can you please rephrase your question more precisely.