Что такое нормальные алгорифмы Маркова? Душкин объяснит

Подписаться 14 тыс.

Просмотров 3,9 тыс.

50% 1

Нормальные алгорифмы (алгоритмы) Маркова - это ещё одна Тьюринг-полная вычислительная модель, предложенная советским математиком А. А. Марковым младшим. Рассмотрим и её.
Заходите на мой ТГ-канал: t.me/drv_official - на нём много всего интересного: анонсы видео, истории и всякий сторителлинг, объявления о мероприятиях и всякое такое разное.
Курс «Основы искусственного интеллекта» на Udemy: bit.ly/3BD2I4W

Опубликовано:

3 окт 2024

Ссылка:

Скачать:

Готовим ссылку...

Добавить в:

Мой плейлист

Посмотреть позже

Комментарии : 22

@olegkomlev Год назад

Слово "алгоритм" происходит от имени персидского ученого Аль-Хорезми, который в латинском написании превратился в Algoritmi или Algorismi. Отсюда латинское слово Algorithmus - это наиболее современное написание (ранее были варианты Algoritmus и Algorismus). В греческом слово "алгоритм" записывалось через букву "тета" (Αλγόριθμος). Такие слова, обычно, при заимствовании передаются в русском языке через [ф] (например, "арифметика" или "рифма"). Но в латыни или родственном латинскому языке, обычно, созвучное греческое слово произносится через [т] или [c]. Например, "ритм" (тоже происходит от греческого "рифма", но в русский пришло из латыни или французского). Поэтому когда-то в русском были и "алгорифм" (из греческого) и "алгоритм" (из латыни). Более того, был в это время и 3-й вариант! Сам видел в математическом справочнике 1930-х годов "алгорисм Эуклида", именно так, через "эс".

@dushkin_will_explain Год назад

Прекрасно. Благодарю за дополнение.

@Resident-1337 Год назад

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

@dushkin_will_explain Год назад

Всё так, идеи витали в воздухе.

@olegkomlev Год назад

А почему в левой части правил должно быть "V+"? Разве нельзя пустое слово заменить на что-то? При этом можно считать, что замена самого левого вхождения пустого слова на что-то означает приписывание этого "что-то" слева. Аналогично, на вход НАМ тоже может поступать пустая строка, поэтому на вход подается V*, а не V+.

@dushkin_will_explain Год назад

Потому что пустых слов в каждом (любом) входе бесконечное множество.

@olegkomlev Год назад

@@dushkin_will_explain Для формулы подстановки L-> D, из всех возможных представлений слова V в виде RLS выбирается такое, при котором R - самое короткое. Если L пусто, то самое короткое R - это пустое R. Но тогда неоднозначность для пустого L: V=LRS=LS=LLS=...LLLLLLS, какое L брать? А какая разница? Возьмем любое из бесконечной череды самых левых вхождений - результат замены не изменится. Поэтому и считают "замена пустоты - это приписывание слева". А если не допускать пустой вход, то как быть, если в процессе работы будет пустое слово? Какая разница, начал НАМ работать с пустым словом или продолжает работать с пустым словом, которое получил в процессе? В любом случае это нужно как-то предусмотреть, значит на вход в общем случае подается V*.

@dushkin_will_explain Год назад

@@olegkomlev, либо это правило должно быть последним в списке и быть с точкой, либо НАМ никогда не остановится же. И моя математическая интуиция мне подсказывает, что это не увеличивает вычислительную силу ну никак, а потому V+ достаточно.

@olegkomlev Год назад

@@dushkin_will_explain В Википедии в статье НАМ сказано "L, D - любые слова". Многие НАМ кончаются правилом вида "-> a" (стрелка без точки!), где а-некий вспомогательный знак ("челнок"). Исполнение алгоритма начинается с того, что слева к слову приписывается этот "а", а потом в начале алгоритма есть правила, по которым этот челнок идет слева направо и заменяет по пути символы. Вроде бы, даже в первоначальной статье Маркова этот прием с челноком приведен.

@dushkin_will_explain Год назад

@@olegkomlev, как челнок «пойдёт слева направо», если правило применяется к самому левому вхождению слова, то есть последнее правило типа (-> a) будет бесконечно применяться к началу строки?

@dushkin_will_explain Год назад

Все видео канала по искусственному интеллекту: ru-vid.com/video/%D0%B2%D0%B8%D0%B4%D0%B5%D0%BE-n3wEM7P11kI.html Вы всегда можете обратиться к нам за консультациями.

@dushkin_will_explain Год назад

И, кроме того, вы всегда можете написать мне в ТГ: @rdushkin

@dushkin_will_explain Год назад

Изображение с доски: disk.yandex.ru/i/ArUM4WtYJlirBA