「自然な」決定不可能な言語はありますか？

Question

抱えていない「自然な」言語はありますか？

「ナチュラル」とは、マシンとそれらの同等物を介してではなく、文字列の特性によって直接定義される言語を意味します。言い換えれば、言語が$$ l = { langle m rangle mid ldots } $$のように見える場合、$ m $はtm、dfa（または通常のexp）、pda（または文法）、など..、$ l $ ではありません ナチュラル。ただし、$ l = {xy ldots mid x text {はy} ldots } $のプレフィックスです。

Answer 1

あなたは「文字列」が欲しかったので、私は古典的なものについて言及します： 対応の問題を投稿します.

Answer 2

がある 多くの例 しかし、ここにいくつかあります：

• の言語の真の文のセット 算術 決定不可能です。

• SET理論（ZFC）の一連の証明された文章は決定できません。

• 解を持っているディオファンティン方程式のセットは習得不可能です。