Проблема разрешения

Проблема разрешения (нем. Entscheidungsproblem) — задача из области оснований математики, сформулированная Давидом Гильбертом в 1928 году: найти алгоритм, который бы принимал в качестве входных данных описание любой проблемы разрешимости (формального языка и математического утверждения «<math>S</math>» на этом языке) — и, после конечного числа шагов, останавливался бы и выдавал один из двух ответов: «Истина!» или «Ложь!», — в зависимости от того, истинно или ложно утверждение «<math>S</math>». Ответ не требует обоснований, но должен быть верным.

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

В 1936 году — Алонзо Чёрч и независимо от него Алан Тьюринг опубликовали работы, в которых показали, что не существует алгоритма для определения истинности утверждений арифметики, а поэтому и более общая проблема разрешения также не имеет решения. Этот результат получил название: «теорема Чёрча — Тьюринга».

Литература

• Alonzo Church An unsolvable problem of elementary number theory // American Journal of Mathematics. — 1936. — Vol. 58. — P. 345—363. — DOI:10.2307/2371045.
• Alonzo Church A note on the Entscheidungsproblem // Journal of Symbolic Logic. — 1936. — Vol. 1. — P. 40—41.
• Turing A. M. [www.cs.virginia.edu/~robins/Turing_Paper_1936.pdf On computable numbers with an application to the Entscheidungsproblem] // Proc. London Maths. Soc. (Series 2). — 1936. — Vol. 42. — P. 230—265. — DOI:10.1112/plms/s2-42.1.230.
• Turing, A. M. (1938). «[www.turingarchive.org/viewer/?id=466&title=02 On Computable Numbers, with an Application to the Entscheidungsproblem. A Correction]». Proc. London Maths. Soc. (Series 2) 43: 544—546. DOI:10.1112/plms/s2-43.6.544.

Отрывок, характеризующий Проблема разрешения

Пьера с тринадцатью другими отвели на Крымский Брод, в каретный сарай купеческого дома. Проходя по улицам, Пьер задыхался от дыма, который, казалось, стоял над всем городом. С разных сторон виднелись пожары. Пьер тогда еще не понимал значения сожженной Москвы и с ужасом смотрел на эти пожары.
В каретном сарае одного дома у Крымского Брода Пьер пробыл еще четыре дня и во время этих дней из разговора французских солдат узнал, что все содержащиеся здесь ожидали с каждым днем решения маршала. Какого маршала, Пьер не мог узнать от солдат. Для солдата, очевидно, маршал представлялся высшим и несколько таинственным звеном власти.
Эти первые дни, до 8 го сентября, – дня, в который пленных повели на вторичный допрос, были самые тяжелые для Пьера.

Х
8 го сентября в сарай к пленным вошел очень важный офицер, судя по почтительности, с которой с ним обращались караульные. Офицер этот, вероятно, штабный, с списком в руках, сделал перекличку всем русским, назвав Пьера: celui qui n'avoue pas son nom [тот, который не говорит своего имени]. И, равнодушно и лениво оглядев всех пленных, он приказал караульному офицеру прилично одеть и прибрать их, прежде чем вести к маршалу. Через час прибыла рота солдат, и Пьера с другими тринадцатью повели на Девичье поле. День был ясный, солнечный после дождя, и воздух был необыкновенно чист. Дым не стлался низом, как в тот день, когда Пьера вывели из гауптвахты Зубовского вала; дым поднимался столбами в чистом воздухе. Огня пожаров нигде не было видно, но со всех сторон поднимались столбы дыма, и вся Москва, все, что только мог видеть Пьер, было одно пожарище. Со всех сторон виднелись пустыри с печами и трубами и изредка обгорелые стены каменных домов. Пьер приглядывался к пожарищам и не узнавал знакомых кварталов города. Кое где виднелись уцелевшие церкви. Кремль, неразрушенный, белел издалека с своими башнями и Иваном Великим. Вблизи весело блестел купол Ново Девичьего монастыря, и особенно звонко слышался оттуда благовест. Благовест этот напомнил Пьеру, что было воскресенье и праздник рождества богородицы. Но казалось, некому было праздновать этот праздник: везде было разоренье пожарища, и из русского народа встречались только изредка оборванные, испуганные люди, которые прятались при виде французов.
Очевидно, русское гнездо было разорено и уничтожено; но за уничтожением этого русского порядка жизни Пьер бессознательно чувствовал, что над этим разоренным гнездом установился свой, совсем другой, но твердый французский порядок. Он чувствовал это по виду тех, бодро и весело, правильными рядами шедших солдат, которые конвоировали его с другими преступниками; он чувствовал это по виду какого то важного французского чиновника в парной коляске, управляемой солдатом, проехавшего ему навстречу. Он это чувствовал по веселым звукам полковой музыки, доносившимся с левой стороны поля, и в особенности он чувствовал и понимал это по тому списку, который, перекликая пленных, прочел нынче утром приезжавший французский офицер. Пьер был взят одними солдатами, отведен в одно, в другое место с десятками других людей; казалось, они могли бы забыть про него, смешать его с другими. Но нет: ответы его, данные на допросе, вернулись к нему в форме наименования его: celui qui n'avoue pas son nom. И под этим названием, которое страшно было Пьеру, его теперь вели куда то, с несомненной уверенностью, написанною на их лицах, что все остальные пленные и он были те самые, которых нужно, и что их ведут туда, куда нужно. Пьер чувствовал себя ничтожной щепкой, попавшей в колеса неизвестной ему, но правильно действующей машины.