Удвоение (дублирование, однократное копирование) чисел в унарной системе счисления

Как видим, алфавит (внешний алфавит) машины Тьюринга включает в себя только один символ: " 1 ". Перечень Инструкций (внутренний алфавит) состоит из 9 состояний (8 + 1), где Q0 - это остановка. В каждом состоянии в таблице содержится предписание выполнить то или иное действие при считывании соответствующего символа: " 1 " или " _ " (пустой ячейки).

После запуска машины, в состоянии Q1 головка считывающего устройства движется в к крайней справа единице, о чём машина "узнает", считав первую пустую ячейку в этом состоянии. Тогда она переходит в состояние Q2, в котором начинается её работа с единицами из состава исходного числа - каждую из них нужно обозначить как скопированную (Q3) и продублировать в конце копии справа (Q4).

В связи со скорым началом нового учебного года 🎄изложим отдельные пункты плана нашего курса Логики:

Исчисление высказываний.
В рамках этого раздела науки Логики выделяем четыре теории и, соответственно, столько же аспектов его изучения: 1) элементарная логика высказываний, или теория истинностных функций, или классическая логика высказываний - построение исчисления высказываний модельно-теоретическим способом; 2) алгебра высказываний, или булева алгебра; 3) дедуктивная логика высказываний - формальная система с постулатами исчисления высказываний; 4) метаматематика исчисления высказываний - исследование свойств полноты и непротиворечивости.

Элементарная логика высказываний.
Символы элементарной логики высказываний: пропозициональные буквы, пропозициональные связки, скобки. Формулы как разновидность непустых последовательностей символов. Правила образования формул. Виды формул: тождественно истинные, тождественно ложные и нейтральные; выполнимые и невыполнимые. Способы установления вида формул: 1) таблицы истинности. Целесообразность - определение правильности рассуждений (умозаключений). Нормальные формы формул исчисления высказываний, дизъюнктивная и конъюнктивная нормальные формы, совершенные дизъюнктивная и конъюнктивная нормальные формы, сокращённые нормальные формы формул. Способы установления вида формул: 2) эквивалентные преобразования в совершенные нормальные формы.

Вспомним основные равносильности - эквивалентные преобразования одних формул в другие:

Итак, в новом курсе для первокурсников думаю озвучить следующие темы: Тезис Чёрча-Тьюринга об эквивалентности теорий Рекурсивных функций, Машин Тьюринга, Вычислимых функций и Алгорифмов Маркова; его критика с позиций Счётных бесконечных множеств, Унарной системы счисления и Формальной арифметики Пресбургера (арифметики без знаков для операций умножения и возведения в степень).
Будем строить Формальную систему, в которой нет несчётно бесконечных множеств, а значит - ВСЁ доказуемо или опровержимо, вычислимо и реализуемо на машинах Тьюринга. Это - возвращение к принципам Логицизма, где всё однозначно предопределено Логикой ("Логика - это тот план, по которому Бог строит мир" Гегель).

Каждому первокурснику - формулу из Доказательства (или опровержения) теоремы Ферма 😁 используем Диагональный метод Кантора в полную силу - математической индукцией по 4 переменным (у Гёделя только 3 😢 в его знаменитых теоремах о невозможности одновременного доказательства полноты и непротиворечивости формальных систем Пеано и Рассела-Уайтхеда).

Используем мощь образовательной системы во имя Науки (аналогия из сериала "Задача трёх тел", когда игровой Фон Нейман через Императора побуждает китайских военнослужащих выполнять функции логических элементов цифровой системы его имени).

P.S. Честно говоря, я удивлен тому, что Клини осталось в своё время сделать только шаг - индукция по 4 переменным - для решения теоремы Ферма, а он его не сделал...

#ЛогикаМетаматематика
Логика - это наука о формах и приёмах мышления (рационального познания). Выделяют три основных формы мышления: понятие, высказывание (суждение), умозаключение (рассуждение). Они основные в том смысле, что представляют собой простейшие составляющие любых рациональных познавательных форм (структур) и приемов (методов, процедур), таких как: определения, классификации, правила образования (простейших и сложных значимых выражений), правила преобразования (аксиомы и правила вывода прямые и производные, дедуктивные и индуктивные) и теории. Свойства теорий, например, изоморфизм, полнота и непротиворечивость изучаются в метаматематике.

Поздравляю всех с полным лунным затмением! (Сейчас пока ещё наблюдаемым)

Когда мы рассматриваем логику, следуя традиции, начатой в 4-3 веках древнегреческими философами-стоиками, продолженной Кантом и Гегелем и отражающейся в существовании логики как отдельной специальности философских наук, как один из разделов философии, наряду с философией природы (физикой) и философией духа (этикой), мы следуем общепринятой сегодня в науке и эпистемологии установке. Когда мы рассматриваем логику как первый раздел философии, мы следуем традиции немецкой классической философии (а именно учений Канта, Фихте, Шеллинга и Гегеля) - и в этом особенность нашего подхода. Своеобразие и единичность (обычно говорят "уникальность") в том, что мы ограничиваем наши содержательные исследования счётными множествами (в теории моделей) и утверждаем возможность доказательства полноты и непротиворечивости исчисления предикатов как формальной дедуктивно-аксиоматической системы (в теории доказательств), возрождая тем самым логицизм Лейбница.

Блжайшим образом мы будем рассматривать исчисление высказываний и исчисление предикатов как они предстают в четырёх версиях: 1) в теории моделей - элементарная логика высказываний и элементарная логика предикатов с предметными переменными и предметными константами. Здесь мы будем использовать метод таблиц истинности для решения вопроса о том, является ли та или иная формула тождественно истинной или нет в исчисления высказываний, а в исчислении предикатов метод совместных таблиц истинности, включающий распределение значений предметных переменных и n-местных предикатных форм, содержащих варьирование значений предметных переменных. Также в исчислении предикатов нам потребуется указание на количество объектов рассматриваемой предметной области, для того, чтобы ввести понятие k-тождественно истинной и общезначимой формулы.

2) В алгебре высказываний и алгебре предикатов - теориях эквивалентных преобразований соответствующих формул, в которых теоретические и прикладные задачи, стоящие перед логикой, мы будем решать методом сведения формулы к совершенной дизъюнктивной и совершенной конъюнктивной нормальным формам в исчислении высказываний и предваренной и скулемовской нормальным формам в исчислении предикатов.