Как в русскоязычной литературе называется Smn теорема? https://en.wikipedia.org/wiki/Smn_theorem

В книге Шеня и Верещагина https://mccme.ru/free-books/shen/shen-logic-part3-2.pdf я не нашел такой теоремы. Они вообще без неё обходятся? Или она называется как-то по-другому? Или есть какое-то похожее утверждение, которое они используют? Или эта теорема вообще ни для чего не нужна?

задан 23 Май 6:54

изменен 23 Май 6:56

Последняя фраза, на мой взгляд, находится ближе всего к истине :)

(24 Май 5:02) falcao

Но это странно. В книге Hartley Rogers (а это был один из главных людей в теории вычислимости, позаметнее Шеня или Верещагина) "Theory of Recursive Functions and Effective Computability" я вижу очеь много отсылок к Smn теореме.

(25 Май 9:31) logic

Да вы, батенька, крупный спец, "позаметнее" Hartley Rogers будете.

А такие вопросы у нас, дилетантов, спрашиваете.

(25 Май 14:31) FEBUS

@logic: я могу Вам это явление легко объяснить. Любой крупный специалист, когда пишет учебник, считает своим долгом воспроизвести все считающиеся значимыми результаты предшественников. Сюда, вне сомнения, входят результаты крупных математиков типа Клини. Беда которых в том, что они были "пионерами" в своей области, и излагали всё в чудовищных обозначениях. Это неизбежное явление -- посмотрите хотя бы формулировки великого Гёделя. И, пока это не "осовременить", читать и изучать подобные вещи невозможно. Возьмите хотя бы старый учебник Клини -- это ведь полная "клиника"! :)

(25 Май 14:57) falcao

@falcao Но он не просто излагает Smn Теорему, а использует её повсеместно, включая непродвинутые результаты. Не может же быть так, что это теорема вдруг стала бесполезной и не используется в книге Шеня-Верещагина. Кроме того, многие современные тексты её используют, в т.ч. русскоязычные (описывая её как "принадлежащую к числу основных результатов теории алгоритмов"):

https://studfile.net/preview/3373080/page:3/

http://shorturl.at/sJOY5

https://www.nsu.ru/n/mathematics-mechanics-department/documents/algorithmskogabaev.pdf

http://www.math.nsc.ru/LBRT/logic/aml/programs/mal1-w.html

(25 Май 20:10) logic

@logic: Вы задаёте весьма резонные вопросы, и для подробного объяснения тут нужен довольно обстоятельный ответ, который в комментарий не вместится. Я постараюсь чуть позже обрисовать всю эту ситуацию.

(25 Май 21:18) falcao

Вот, например, теорема о существовании главной универсальной вычислимой функции (насколько я понимаю, это она, или нет?) доказывается с помощью Smn Теоремы https://i.stack.imgur.com/XNoTf.png

Можно сравнить с доказательством теоремы на стр.24-25 В-Ш. https://mccme.ru/free-books/shen/shen-logic-part3-2.pdf Я там не нашел никакого аргумента, похожего на Smn теорему.

(26 Май 0:23) logic
показано 5 из 7 показать еще 2
10|600 символов нужно символов осталось
0

Предлагаю начать с одного места в тексте книги В. и Ш., чтобы была понятна дальнейшая мысль. Это начало страницы 9, пункт 4. Я имею в виду "пассаж" по поводу компьютерной грамотности.

Теперь сравните это с тем, чтобы было "на заре" развития теории алгоритмов. Тогда ни одного (!) языка программирования не существовало. И одной из главных целей теории было дать формальное определение алгоритма. Потом были предложены: понятие рекурсивной функции, понятие машины Тьюринга, определение на основе лямбда-исчисления, нормальные алгорифмы Маркова, и куча всего другого. Оказалось, что все эти определения в неком смысле эквивалентны, то есть дают один и тот же класс вычислимых функций. Появился тезис Чёрча, он же тезис Чёрча - Тьюринга, а иногда упоминают ещё и имя Клини.

Теперь обратимся к сути Smn-теоремы. Достаточно рассмотреть случай m=n=1 для иллюстрации. Есть программа вычисления функции f(x,y). Она написана на каком-то "языке программирования". Возьмём для примера что-то типа упрощённого Паскаля. У Вас есть текст программы. Вам говорят: нас будет интересовать только случай x=3, и использовать мы хотим программу нахождения f(3,y). Перепишите, пожалуйста, код.

Что Вы будете делать? Откроете в редакторе текст программы. Там увидите команды ввода типа

readln(x);

readln(y);

...

Замените первую запись на x:=3, нажмёте Save, и компилятор создаст новый exe-файл.

Больше ничего за этой теоремой не скрывается. Важно лишь то, что если программа -- это её номер, или текст в машинных кодах, то процедура замены одного на другое алгоритмична (хотя тексты меняются довольно сильно), и сама может быть осуществлена машиной (программой). И если Вас спросят: "а можете ли Вы написать нам такую программу?", то понятно, что можете, но это долгая механическая работа. Надо искать подстроку текста с readln, менять её на другие символы, и всё это в виде гёделевых номеров, или в виде кодов последовательностей. Сделать это можно, и все понимают, как делать, но задание -- оно типа "десять тысяч раз присесть".

По тем или иным причинам, "пионеры" теории алгоритмов так и "приседали". Например, Марков разработал своё исчисление, а потом на этом языке написал в явном виде программу типа "компилятора". Это большой ручной труд, он вызывает уважение, но повторять такое в наше время, или даже просто перепроверять те выкладки, мало у кого будет желание.

Именно об этом и пишут авторы современной книги. Они где надо свободно опираются на тезис Чёрча, и не выписывают в формальном виде универсальную функцию на языках программирования "низкого уровня" типа машин Тьюринга.

Поэтому "с высоты" нынешнего уровня развития алгоримизации, какими-то вещами и в самом деле можно "пожертвовать". Важно то, что происходит не отказ от знания каких-то важных истин науки, а всего лишь отказ от бесполезных "приседаний".

При этом сам формальный аспект никуда не девается, и его надо высвечивать там, где это необходимо, но в отношении к программам определённого типа, сейчас стало вполне стандартным ограничиваться словесными описаниями программ, и инструкциями по поводу того, как их можно было бы создать. Согласитесь, что чтение 100-страничного машинного кода не принесёт ровно никакой пользы, и не добавит ни строгости, ни убедительности.

ссылка

отвечен 26 Май 1:09

10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×883

задан
23 Май 6:54

показан
107 раз

обновлен
26 Май 1:09

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru