Является ли этот язык разрешимым?

Я борюсь с тем, разрешимо ли это:

A = {x является элементом множества натуральных чисел | для каждого y большего, чем x, 2y является суммой двух простых чисел}

Я склонен думать, что это разрешимо, учитывая тот факт, что при вводе в машину Тьюринга она никогда не достигнет состояния принятия и цикла до бесконечности, если только не отклонит. Однако я также знаю, что для того, чтобы язык был разрешимым, должен существовать только алгоритм, решающий его; нам не обязательно знать, как это делается. При этом часть меня думает, что это разрешимо? Кто-нибудь знает, как доказать?


math primes theory turing-machines decidable
person user1171851    schedule 26.01.2012    source источник

Ответы (1)


arrow_upward
7
arrow_downward

Этот язык разрешим, хотя доказательство немного злое.

Для начала давайте подумаем о свойствах этого языка. Ясно, что если n — натуральное число, содержащееся в языке, то каждое число больше n также содержится в языке. Таким образом, этот язык может принимать три возможные формы:

  1. Этот язык содержит все натуральные числа или
  2. Этот язык не содержит натуральных чисел или
  3. Этот язык содержит все натуральные числа, большие некоторого натурального числа n.

Языки (1) и (2) — это, соответственно, {0, 1}* и пустой язык, оба из которых разрешимы (поэтому существуют ТМ, которые всегда останавливаются и принимают эти языки). Каждый язык формы (3) также разрешим, потому что для любого n мы можем легко написать НП с жестко запрограммированным в нем n, который просто проверяет, не меньше ли входных данных n. Следовательно, независимо от того, какой случай верен (1, 2 или 3), существует некоторая ТМ, которая всегда останавливается, чей язык является языком, который вы предоставили, поэтому ваш язык разрешим.

Но, тем не менее, это доказательство неконструктивно. Мы можем показать, что язык должен быть разрешимым, но на самом деле мы не можем найти ТМ, который всегда останавливается и принимает его! На самом деле, никто не знает, что это за ТМ, потому что гипотеза Гольдбаха (каждое ли четное число сумма двух простых чисел больше двух) — открытая проблема математики.

Надеюсь это поможет!

person templatetypedef    schedule 26.01.2012