Что такое нормальные алгорифмы Маркова? Душкин объяснит
HTML-код
- Опубликовано: 3 окт 2024
- Нормальные алгорифмы (алгоритмы) Маркова - это ещё одна Тьюринг-полная вычислительная модель, предложенная советским математиком А. А. Марковым младшим. Рассмотрим и её.
Заходите на мой ТГ-канал: t.me/drv_official - на нём много всего интересного: анонсы видео, истории и всякий сторителлинг, объявления о мероприятиях и всякое такое разное.
Курс «Основы искусственного интеллекта» на Udemy: bit.ly/3BD2I4W
Слово "алгоритм" происходит от имени персидского ученого Аль-Хорезми, который в латинском написании превратился в Algoritmi или Algorismi. Отсюда латинское слово Algorithmus - это наиболее современное написание (ранее были варианты Algoritmus и Algorismus). В греческом слово "алгоритм" записывалось через букву "тета" (Αλγόριθμος). Такие слова, обычно, при заимствовании передаются в русском языке через [ф] (например, "арифметика" или "рифма"). Но в латыни или родственном латинскому языке, обычно, созвучное греческое слово произносится через [т] или [c]. Например, "ритм" (тоже происходит от греческого "рифма", но в русский пришло из латыни или французского). Поэтому когда-то в русском были и "алгорифм" (из греческого) и "алгоритм" (из латыни). Более того, был в это время и 3-й вариант! Сам видел в математическом справочнике 1930-х годов "алгорисм Эуклида", именно так, через "эс".
Прекрасно. Благодарю за дополнение.
А почему в левой части правил должно быть "V+"? Разве нельзя пустое слово заменить на что-то? При этом можно считать, что замена самого левого вхождения пустого слова на что-то означает приписывание этого "что-то" слева. Аналогично, на вход НАМ тоже может поступать пустая строка, поэтому на вход подается V*, а не V+.
Потому что пустых слов в каждом (любом) входе бесконечное множество.
@@dushkin_will_explain Для формулы подстановки L-> D, из всех возможных представлений слова V в виде RLS выбирается такое, при котором R - самое короткое. Если L пусто, то самое короткое R - это пустое R. Но тогда неоднозначность для пустого L: V=LRS=LS=LLS=...LLLLLLS, какое L брать? А какая разница? Возьмем любое из бесконечной череды самых левых вхождений - результат замены не изменится. Поэтому и считают "замена пустоты - это приписывание слева". А если не допускать пустой вход, то как быть, если в процессе работы будет пустое слово? Какая разница, начал НАМ работать с пустым словом или продолжает работать с пустым словом, которое получил в процессе? В любом случае это нужно как-то предусмотреть, значит на вход в общем случае подается V*.
@@olegkomlev, либо это правило должно быть последним в списке и быть с точкой, либо НАМ никогда не остановится же. И моя математическая интуиция мне подсказывает, что это не увеличивает вычислительную силу ну никак, а потому V+ достаточно.
@@dushkin_will_explain В Википедии в статье НАМ сказано "L, D - любые слова". Многие НАМ кончаются правилом вида "-> a" (стрелка без точки!), где а-некий вспомогательный знак ("челнок"). Исполнение алгоритма начинается с того, что слева к слову приписывается этот "а", а потом в начале алгоритма есть правила, по которым этот челнок идет слева направо и заменяет по пути символы. Вроде бы, даже в первоначальной статье Маркова этот прием с челноком приведен.
@@olegkomlev, как челнок «пойдёт слева направо», если правило применяется к самому левому вхождению слова, то есть последнее правило типа (-> a) будет бесконечно применяться к началу строки?
Интересно, Марков знал о Машине Тьюринга когда изобрел свой "алгорифм"? Не факт, кстати, просто эти идеи витали в воздухе в то время, Чёрч тоже примерно в то время же творил
Всё так, идеи витали в воздухе.
Все видео канала по искусственному интеллекту: ruclips.net/video/n3wEM7P11kI/видео.html
Вы всегда можете обратиться к нам за консультациями.
И, кроме того, вы всегда можете написать мне в ТГ: @rdushkin
Изображение с доски: disk.yandex.ru/i/ArUM4WtYJlirBA
жирный лайк за алгориФм
Ну а как иначе? :)
@@dushkin_will_explain в ностальгию запал ))) в институте курсовую по этой теме делал, а код писал на турбо паскале 7
@@darkshaman766, прекрасно :)
Похоже на префиксное кодирование
Есть такое.