Lesson 6. Finite machines

[the-homeless-god]

1. Draw an example for determined and non-determined finite machine (paste a picture with explanation)
2. What's Lambda Calculus?
3. What's difference between Church & Turing ideas for lambdas?
4. What's AST (abstract syntax tree)? Provide the real life example
5. What's a number?

[SergeyLeMoNChik]

Детерминированная конечная машина - машина, в которой для каждого состояния и каждого символа входного алфавита есть точно одно следующее состояние. Значит, при получении определенного символа, происходит переход в одно и то же следующее состояние.
Недетерминированная конечная машина - машина, в которой для каждого состояния и каждого символа входного алфавита может быть несколько следующих состояний. Значит, при получении определенного символа может произойти переход в несколько следующих состояний.
2. Лямбда-исчисление - это математическая система, которая позволяет оперировать функциями, не привязывать их к конкретным именам, а использовать анонимные выражения.
3. Идеи Черча и Тьюринга для лямбда-выражений имеют различия в основном в подходе к представлению и применению функций. Черч предлагает представлять функции с помощью лямбда-выражений и применять их путем подстановки значений аргументов в выражения. Тьюринг, с другой стороны, предлагает представлять функции как последовательности инструкций и применять их путем выполнения этих инструкций.
4. AST - дерево показывающее всевозможные наборы соединения частей алфавита воедино
Пример: имеем алфавит буа
все 3 буквенные слова начиная с буквы б

5. Число – одно из понятий в математике, которое используется для счёта, измерения, сравнения, выполнения каких-либо математических операций. Числа могут быть натуральными, дробными, положительными, отрицательными и т.д. А ещё числа состоят из цифр)

[Chayz1337]

1.Детерменированный автомат. Он пребывает только в одном состоянии в определенный период времени и никак иначе.

Недетерменированный автомат. Он может пребывать в нескольких состояниях сразу в определенный момент времени.

2.Лямбда исчисление – это своего рода «анонимная» функция. А анонимная она потому что у нее нет имени, арифметических операций, циклов, констант, онли фукнции.
3. В отличие друг от друга, лямбда-исчисление фокусируется на функциональных вычислениях и работе с функциями, в то время как машина Тьюринга представляет собой последовательную модель вычислений с конечным набором инструкций и состояний.
4. AST – способ организации программы в виде дерева.

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

[EwvwGeN]

Детерминированная

Недетерминированная

2. Лямбда-исчисление - набор правил, как ни странно для формального представления вычислений. В таких вычислениях используются лямбда-выражения или, другими словами, те же анонимки, как писали выше.
3. Черч выводил более частный случай, пытаясь оперировать натуральными числами. Тьюринг же включал все возможные виды чисел начиная натуральными, заканчивая вещественными.
4. Абстрактное синтаксическое дерево - дерево, отображающее возможное продолжение от текущей точки на основе какого-то алфавита. При этом чаще используются не просто буквы алфавита, а полноценные токены.
   Пример, у нас есть слово "искать", дальше не может пойти любая буква алфавита, а только соответствующий токен - подходящее слово или предлог: "искать работ", "искать по работе".
5. Число - способ описания всего. Задается набором цифр и математическими операциями.

[V1taly5]

1. Draw an example for determined and non-determined finite machine (paste a picture with explanation)
   
   На первом рисунке показано, что из вершины S₀ существует только один переход с 1, может существовать другой переход, к этой же вершине (или другой), но не с 1.
   А на втором рисунке показано, противоположное, что из вершины S₀ по переходу с 1 можно попасть в разные состояния ( S₁, S₀ ). Это обосновано тем, что в детерминированном автомате: следующее состояние однозначно определяется, текущим его состоянием и входным символом. А Недетерминированные автомат может переходить в разные состояния вод воздействием одного и того же входного символа.

2. What's Lambda Calculus?
   Лямбда-исчисление - это некая система, которая может быть использована для представления различных вычислений и/или операций.

3. What's difference between Church & Turing ideas for lambdas?

• Черча описывал Лямбда-исчисление на функциях и их применении. Это как набор правил для работы с функциями без имени.
• Тьюринг описывал свою машину как упрощенный компьютер, который бы читал и записывал символы на ленте по определенным правилам.
  Обе идеи схожи в том, что любые вычисления можно представить в виде этих абстрактных систем.

4. What's AST (abstract syntax tree)? Provide the real life example
   AST дерево - это некая структуризация информации в виде дерева, в котором узлами представлены операции или элементы, а связь между ними определяет их иерархию.
   В качестве жизненного примера AST дерева могу привести, любую инструкцию, ее можно представить в виде AST дерева, где каждый узел будет представлять отдельный шаг в процессе сборки.

5. What's a number?
   Число - это математическая абстракция, которая представляет собой концепцию количества или величины.

[AlexeyOvsyanniko]

Детерменированная конечная машина - это машина в которой каждое последующее состояние имеет только одну вариацию, что обеспечивает полную предсказуемость.

Недетерминированная конечная машина - это машина это машина в которой каждое последующее состояние имеет несколько вариаций.

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

Если учитывать тот факт что они взаимозаменяемы, то отличаться они будут только по структуре.
Машину Тьюринга можно представить в виде неограниченного кортежа из ячеек, в то время как лямбда исчисление(Church) представляет собой выражение.

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

Номер это способ что-то идентифицировать, классифицировать или описать количество.

[NikitaZhulenkov]

1. Нарисуйте пример для детерминированной и недетерминированной конечной машины (вставьте картинку с пояснением)
   
   Детерминированный автомат может находиться только в одном состоянии в данный момент времени.
   
   Недетерминированный автомат может находиться только в нескольких состояниях сразу.

2. Что такое лямбда-исчисление?
   Лямбда-исчисление – это формальная система, придуманная американским математиком и логиком Алонзо Черчем в 1930-х годах для определения любой языковой конструкции или алгоритма.

3. В чем разница между идеями Черча и Тьюринга для лямбд?
   Идеи Черча и Тьюринга для лямбд различаются в подходах к формализации вычисления функций. Черч вычислял функции с помощью лямбда-исчислений. Тьюринг использовал свою машину для вычисления функций в виде последовательности переходов состояний алгоритма.

4. Что такое AST (абстрактное синтаксическое дерево)? Приведите пример из реальной жизни
   AST (Абстрактное синтаксическое дерево) – структура данных, представляющая собой в виде дерева и работающая как один из промежуточных слоев при преобразовании языков высокого уровня.
   В качества примера из жизни была взята сборка модели из конструктора лего, где, следуя по инструкции пошагово, к каждой детали прикрепляется еще одна деталь.

5. Что такое число?
   Число – это одно из основных понятий математики, отображающее количество или порядок по счету.

[1Waldemar1]

1. На будущее детерминированного конечного автомата влияет только его прошлое состояние и вводные данные. А в недетерминированные конечные автоматы одновременно может быть несколько возможных переходов из одного состояния по одним и тем же входным данных.
   
2. Лямбда-исчисление - это математическая система, где выражения создаются и управляются с помощью набора определенных правил.
3. Идеи Черча основаны на абстракциях функций, а машины Тьюринга оперируют над символами на ленте.
4. AST (абстрактное синтаксическое дерево) - это способ представления структуры программного кода в виде дерева. Например, карта метро, которая показывает станции, линии и соединения между ними.
5. В материальном мире как таковых чисел не существует, это лишь абстракция, придуманная человеком для описания окружающего нас мира.

[Mirra04]

1. Детерминированная конечная машина может пребывать только в одном состоянии в конкретный момент времени. Также для определенного входного символа есть только одно следующее состояние.
   
   Недетерминированная конечная машина может пребывать нескольких состояниях одновременно. Также для определенного входного символа есть несколько следующих состояний.
   

2. Лямбда исчисление - анонимная (потому что нет имени) функция, в которой есть аргумент и некоторые параметры.
   Например: (λx.x^2)3
   После вычислений получится 9

3. • Чёрч рассматривал только функции положительных целых чисел, тогда как Тьюринг охватывал и целые, и действительные.

• Лямбда исчисления ориентированы на функции, а машина Тьюринга на последовательность действий.
• Лямбда исчисления представляют собой функцию, а машина Тьюринга – это бесконечная лента с автоматом для чтения и записи, а также программой для решения того что нужно делать.

4. AST - абстрактное древовидное представление программного кода.
   Пример:
   Приготовление пиццы:
   
   x^2+4x-6
   

5. Число – количественная характеристика для сравнения, измерения, счета, нумерации, вычислений. Для записи чисел используются цифры. Числа есть натуральные, целые, рациональные, действительные (вещественные), комплексные.
   Если нужно что-то философское: числа являются важным компонентом в «построении» мира (хоть и достаточно абстрактным, ведь кто-то в любой момент может сказать и доказать, что 1 метр равен не 100 см, а 10, и тогда все наше привычное устройство мира переменится). Без чисел мы бы не смогли ориентироваться во времени, часовых поясах, измерять что-либо (линейка, рулетка), строить здания, пользоваться деньгами. С помощью чисел мы можем интерпретировать мир. Поэтому числа являются одним из ключей к пониманию мира.

[Gv1don]

1. Детерминированный конечный автомат это математическая модель имеющая начальное из которого можно прийти в конечное строго определённым путём без выбора и неопределённости на всём его протяжении. Простыми словами при одних и тех же входных параметрах происходят одни и те же операции (проходится один и тот же путь).
   

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

2. Я не знал точного определения и не использовал данное понятие, но почитав в интернете понял следующее. Лямбда-исчисление - это использованиея более простых атомарных функций для создания более сложных функций и асбтракций. Например возведение в квадрат как отдельную операцию можно представить как умножение числа и применение этой функции (умножение числа) для аргумента x следующим образом -> x (умножение числа) x.

3. Без понятия.

4. Я не знал точного определения и не использовал данное понятие, но почитав в интернете понял следующее. AST - это дерево, которое отображает структуру функции, то есть операторы, операнды и их отношение. ChatGPT привёл такой классный пример, который был для меня понятен (если он ещё и верный, то вообще супер), поэтому приведу его здесь:
   У нас есть функция x * (y + z), передаём параметры 2, 3, 4, соответственно получаем 2 * (3+4), в AST представляем вот так:

   *
  / \
 2   +
     / \
   3    4

5. Условное обозначение количественной меры. В компьютере это набор нулей и едениц или интерпретируемый результат воздействия функции тока на функцию проводимости транзисторов. Есть ток - 1, нет тока - 0. Соответственно все числовые значения согласно двоичной системе счисления представляют собой комбинации символов двоичного алфавита, то есть 0 и 1.

[abbb03]

У нас есть алфавит (конечное множество неделимых символов формального языка) состоящий из 2 символов:

• "НЕ СЪЕЛ БУРБУРОД С СЫРЫМ"
• "СЪЕЛ БУРБУРОД С СЫРЫМ"

Также, есть три состояния ("ГОЛОДЕН", "ПЕЧАЛЕН", "СЧАСТЛИВ")

Детерминированный автомат

У детерминированного конечного автомата переход в каждое из состояний однозначно определен входящим символом.

Недетерминированный автомат

У недетерминированного конечного автомата переход из состояния "голоден" уже не может быть известен, поскольку символ "СЪЕЛ БУРБУРОД С СЫРЫМ" приводит систему не в определенное состояние, а в одно из возможных.

Лямбда-исчисление - это система Черча, рожденная при решении вопроса о существовании алгоритма, за конечное число шагов определяющего истинность или ложность утверждения, записанного на неком формальном языке.

Термы -выражения, вычисление которых даёт значение, которое есть всё тот же терм.

У нас есть алфавит, символы которого что-то значат - это основа, это, так сказать, база, на чем строятся последующие вычисления. Символы алфавита - термы. К символам алфавита мы можем применять функции одного аргумента (эти функции тоже являются термами). Возвращаемое функциями значение - некий терм, что значит, что функция может вернуть как значение, так и функцию, которую можно применить к другому терму.

Функции задаются записью (λx.M), где x - переменная, M - некая функция. Применение функции - (MN), где M- функция, а N - аргумент.

Задаем числа (некоторые скобочки опустил):

s - имя функции инкрементирования (+1)

z - имя функции, которая представляет 0

0 = λs.λz.z - тут мы определяем, что s это 0, который функция (+1)
1 = λs.λz.sz - здесь у нас s уже применяется к z, из-за чего мы получаем функцию +1, в которой уже есть 1
2 = λs.λz.s(sz)
3 = λs.λz.s(s(sz))

Получается, чтобы получить 50 надо сделать следующую функцию:

50 = λnλs.λz.s(nsz), где n - функция λs, применённая к функции λz, представляющей собой начальное значение, n раз.

Задание tru и folse:

tru = λa.λb.a
false = λa.λb.b

Задание if:

if=λp.λt.λe.(pt)e

p - функция предиката (условия)
t - функция, выполняемая если условие истинно
e - функция, выполняемая если условие ложно

У нас выходит:

за t возьмём 1, а за e возьмём 0, тогда

((if tru) 1 0) = ((λt.λe.tru t e 1) 0) = (λe.tru 1 e 0) = (tru 1 0) = (λb.1 0) <- тут получается, что наш tru - это λa.λb.a, где в роли a выступила 1, а значит, что в b пойдёт 0, то есть будет функция вида (1 0), возвращающая 1

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

Вообще, как я понял, лямбды сводятся к машине Тьюринга, как и наоборот.

AST - структура данных, используемая синтаксическим анализатором для представления отношения операторов и операндов согласно грамматике языка.
В реальной жизни это может быть сигнал светофора - оператор (сигнал) определяет отношение операндов (меня и автомобиля) на основе грамматики языка (правила ПДД). То есть простой человекочитаемый знак в нашем мозге обретает некое представление.

5. Число - это абстрактное понятие, исчисляющее что-то. Допустим, число 5 я могу представить в виде пяти камешков, или в виде комбинации пикселей, горящих на экране. Каким бы не было представление данного числа, его понятие неизменно.

[castaval]

1. Draw an example for determined and non-determined finite machine (paste a picture with explanation)
   
   Первая схема является детерминированной, его состояние однозначно определяется текущим состоянием и входящим параметром.
   Вторая схема является недетерминированной, из состояния OFF при входящем параметре ON состояния может быть как Full bright, так и DIM.
   Это не соответствует определению детерминированного конечного автомата.
2. What's Lambda Calculus?
   Лямбда вычисление - это наименьший универсальный язык программирования мира. Он состоят из единиственного правила подстановки переменных и единой схемы определения функции.
   Данный язык универсален в том смысле, что любая вычислимая функция может быть выражена и вычислена используя выше упомянутые правила.
3. What's difference between Church & Turing ideas for lambdas?
   Лямбда вычисления Чёрча эквивалентны машинам Тьюринга, однако лямбда вычисление подчеркивает использование правил преобразования и не заботится о реальной машине, реализуя их. Этот подход больше связан с программным, чем с аппаратным обеспечением.
4. What's AST (abstract syntax tree)? Provide the real life example
   Абстрактная репрезентация структуры программ, сфокусированное на элементах и их отношениях.
   Пример - дом, дерево, иерархия званий в армии, государство.
5. What's a number?
   Число - единица математического языка, позволяющее описывать мир в количественных значениях. Фундамент математики.

[kargadesh]

Слева машина детерминирована, ибо заранее определено из какого состояние в какое машина может перейти и при каких условиях.
Справа недетерминорована, потому что может перейти из состояния 1 как в состояние 2, так и в состояние 3 при одних и тех же условиях. Переход будет осуществляться случайно, то есть неопределённо.

2. Лямбда исчисление - система записи функций. В ней есть лишь абстракции самой функции и её применение к какому-то параметру. В качестве параметра можно передавать другие функции.

3. Не знаю.

4. Abstract syntax tree — представление сложной системы путём её разбиения на более простые элементы и выстраивание из этого дерева.
   Например, любое предложение. "Я налил в чашку чай".
   
   У нас есть сложная система (предложение), мы её разбиваем на менее сложные системы (словосочетания), которые в свою очередь разбиваем на совсем простые элементы (слова). И из этого выстраиваем дерево.

5. Число — удобная для восприятия запись каких-либо значений. Является состоянием функции в какой-то конкретный момент.

[fixat0r]

1.
2. Лямбда-исчисление - математическая штука, которая позволяет нам смотреть на функции как на математические объекты. Мы можем определять и применять функции, основываясь на мат. преобразованиях
3. Черч использовал ляюмбду для создания формальной модели, представляющей алгоритмы и процессы в математике. Тьюринг разрабатывал машину Тьюринга, абстрактную модель для описания алгоритмов и процессов вычислений. Он показал, что эта машина может эмулировать лямбда-исчисление.
В итоге Чёрч использовал лямбда-исчисление для формализации вычислений, а Тьюринг предложил абстрактную модель машины для представления алгоритмов.
4. На любом языке проганья мы применяем команды, которые принимают исходный код и преобразуют в конкретные команды машин. AST дает структурированную визуализацию исходного код, так же благодаря этой штуке компилятор проверяет правильность и корректность использования элементов кода. Потом AST используется для получения байт-кода или машинного кода. Пример применения - AST можно юзать для преобразования кода с одного языка программирования на другой. Пример из жизни: хотим с утра попить водички (исходный код машины(человека) ), значит нужно послать сигнал открыть глазки, подойти к столу, взять стакан, поднести его ко рту и попить(если считать все эти действия командами машины(человека) ).
5. Число по сути является объективной существующей абстракцией. Объективность объясняется тождествами 2+2=4, квадрат гипотенузы равен сумме квадратов катетов. Абстрактность обуславливается тем, что числа по сути только у нас в голове (которая может перегреться, если попробовать визуализировать ∞), эта всемирная договоренность. 2+2=4, а не 5, три взорванные петарды в туалете школы - именно три, а не четыре. В качестве аналогии можно вспомнить температуру замерзания воды в градусах цельсия (0, что собственно и является эталоном) и фаренгейта (32). scio me nihil scire (Я знаю, что ничего не знаю)

[vmishinav]

Нарисуйте пример для детерминированной и недетерминированной конечной машины (вставьте картинку с пояснением).
Детерминированный конечный автомат - модель, где для каждой пары состояние-входной символ существует однозначный переход в следующее состояние.
Недетерминированный конечный автомат - это модель, где для одной пары состояние-входной символ может существовать несколько возможных переходов в различные состояния.

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

В чем разница между идеями Черча и Тьюринга для лямбд?
Лямбда-исчисление (идеи Черча) ориентировано на функциональное программирование и формальность математических функций с помощью абстрактных выражения.
Модель Тьюринга (идеи Тьюринга) ориентирована на процессах универсального вычислительного устройства.

Что такое AST (абстрактное синтаксическое дерево)? Приведите пример из реальной жизни
AST - структура данных, представляющая исходный код программы в виде дерева.
Как пример: распределение студентов по группам/направлениям/ преподавателям и тд, составление расписания. Вообщем не знаю нормального примера.

Что такое число?
Число - данные использумве для измерения и подсчета количества, порядка или качества.