問題タブ [computability]

上記の[タイトル]の記述が正しいかどうか疑問に思っています.

これが私がすでに持っていたものです：非再帰は決定不能を意味します。

私はこれを読みました すべての無限言語は決定不能ですか?

それは言う：

言語が決定不能 (非再帰的) である場合、TM が停止しない原因となる文字列がいくつか存在する必要があります。

これはどのように私の声明[タイトル]を証明できますか? 誰かが私にそれをもう少し明確に説明できますか?

ありがとう

ps。混乱させて申し訳ありません。はい、TMはチューリングマシンを意味します。私の質問は次のとおりです。すべての非再帰言語は無限ですか?

ラムダ計算とチューリングマシンの等価性の証明、および証明の一般的な方法について、一般的な用語で誰かが私に説明できるのではないかと思っています。できるだけ平易な言葉で。

L が任意の言語の場合。言語 perms(L) は、L からの単語のすべての順列の言語です。

正誤問題: L が再帰的に列挙可能 (計算可能) である場合、perms(L) も再帰的に列挙可能です。

これは以前の決勝戦で、L が決定可能であれば perms(L) も決定可能であるという質問とともにありました。これは真実であることがわかりました。

私は間違っていると思いますが、この主張を裏付ける証拠はありません。

私の知る限り、チューリング マシンを作成して、テープにエンコードされた命令のループまたは反復を実行できます。これは、ライン セパレータを特定し、ライン セパレータの特定の数に達するまで (つまり、ループ内で) チューリング マシンを戻すことによって実行できます。しかし、チューリングマシンは再帰プログラムも実行できるのでしょうか?

そのようなチューリングマシンのさまざまな詳細を誰かが説明できますか?

チューリングマシンで再帰が実行できれば、クイックソートも実行できるのではないでしょうか？