37) Теоремы Гегеля

-Множество всех истинных высказываний логики высказываний перечисляемо и разрешимо. Множество всех истинных высказываний логики предикатов перечисляемо (ввиду его полноты), но неразрешимо (ввиду бесконечности предметной области).

-Арифметика и теория чисел являются неаксиматизируемыми теориями, а множество всех истинных высказываний арифметики неперечислимо. Теоремы Гегеля имеют важное методологическое значение: для достаточно богатых математических теорий не существует адекватной формализации. Правда, любую неполную теорию Т можно расширить, добавив к ней в качестве аксиомы истинную, но невыводимую в Т формулу, однако новая теория будет неполна.

Невозможно исследовать метасвойства теории средствами самой формальной теории, т.е всякая метатеория Т для того, чтобы иметь возможность доказывать хотя бы непротиворечивость, должна быть богаче Т.

38) Получение по схеме алгоритма графа эквивалентного автомата.

Далее после схемы алгоритма, необходимо получить ЛСА, МСА, ОГСА(отмеченной), далее строится граф, ОТВЭПВ (обобщенная таблица возбуждения элементов памяти и выходов автомата), затем получают соответственно рабочие и запрещенные обобщенные коды.Далее проводится минимизация полученных переключательных функций методом поразрядного сравнения рабочих и запрещенных обобщенных кодов и возможно получение схемы автомата. Схема может быть получена на основе постоянного запоминающего устройства (ПЗУ), затем полная после получения ОГСА, графа автомата сразу строится таблица программирования ПЗУ: сначала обобщенная, затем полная. По данным таблицы строится схема.

39) Получение по схеме алгоритма переключательных функций эквивалентного автомата.

Далее после схемы алгоритма, необходимо получить ЛСА, МСА, ОГСА(отмеченной), далее строится граф, ОТВЭПВ (обобщенная таблица возбуждения элементов памяти и выходов автомата), затем получают соответственно рабочие и запрещенные обобщенные коды.

40) Получение по схеме алгоритма схемы эквивалентного автомата

41) Рекурсивные ф-ции

Рекурсия – один из основных приемов программирования..Рекурсивные функции – функции, зависящие сами от себя. Функция вычислима, если существует такой алгоритм, то есть пошаговая процедура «от простого к сложному», которая по входному набору переменных вычисляет значение функции ,если этот входной набор принадлежит к области определения функции , или выдает сообщение , что входной набор не принадлежит к области определения функции.

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

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