この言語は決定可能ですか

Question

L = {（ 、 、x）| M1（x）はM2（x）より厳密に多くのステップで実行されます。 （両方の計算が永遠に実行される場合、どちらも厳密に他のものよりも多くのステップを要しません）。

この言語は決定可能ですか？それを証明する方法？

Answer 1

templatypypedefはコメントにヒントがあるため、この言語は決めることができません。決定可能な場合は、次のように停止問題を判断できます。

まず、入力xで停止できないTMをM1とします。そのようなTMは、左右に動いてテープを変えない2つの状態を持つ些細なものでもよい。 M2を任意のTMとする。あなたの言語の決定者は、「すべての入力に対してM2が停止する」という質問に答えることができます。これは停止問題と同じです。また、M2をTMとすることで、特定の入力wがテープ上にあることを最初に確認し、その後いくつかのTM M3に従って続行することができます。これは、問題を「入力停止時にM3が停止する」という問題に変わります。これは、問題のより標準的なバージョンかもしれません。