Теоретическая информатика занимается изучением теории формальных языков , соответственно автоматизации , теории вычислений и сложности , теории графов , криптологии , логики и т. Д. закладывает основу для создания компиляторов для языков программирования и формализации математических задач . Следовательно, это основа информатики.
Автоматы — это теоретические машины в информатике, имеющие четко определенное поведение с помощью ряда правил ( алгоритмов ), составляющих программу . Алгоритм представляет собой конечный набор инструкций, выполнение которых в определенном порядке дает результат.
Конечный автомат имеет цель, начиная с любого состояния, в котором он может находиться в данный момент, достигается конечное состояние, хорошо определяемое программой. Конечно, вы также можете создавать программы со случайными или псевдослучайными элементами.
Машина получает так называемое «входное слово» на входе и, в зависимости от того, что она запрограммирована, выполняет ряд заранее определенных шагов (алгоритмов) для достижения конечного результата. У автомата есть одно стартовое состояние и несколько четко определенных конечных состояний. Как только автомат достиг конечного состояния, пройдя все соответствующие промежуточные состояния, можно сказать, что слово на входе автомата принято. Множество всех слов, принимаемых автоматом, составляет то, что называется языком автомата.
Чтобы иметь возможность принимать сложные языки, необходимы другие модели автоматов, которые сначала должны иметь объем памяти. Набор всех слов, состоящий из последовательности, содержащей равное количество букв «a» и букв «b», составляет так называемый контекстно-независимый язык, для которого требуется «автомат памяти» (также называемый «автоматическое выталкивание вниз »). . Такой автомат имеет в своем распоряжении стопку воспоминаний, с возможностью отмечать, сколько раз буква «а» была прочитана, но еще не связана — и, следовательно, сколько раз буква «б» должна появиться.
Лингвист Ноам Хомски классифицировал формальные языки по иерархии следующим образом:
Обычные языки (английский: обычный язык )
Контекстно-свободный язык (англ .: Context-free Language )
Контекстно-зависимые языки (английский: контекстно-зависимый язык )
Рекурсивно перечисляемый язык ( Recursively enumerable Language )
Вычислительная теория
В теории вычислений теоретическая информатика изучает возможности решения проблемы с помощью определенной машины. В тезисе Курча-Тьюринга утверждается, что любая интуитивная проблема, у которой может быть решение, настолько вычислимое, может быть решена машиной MAA — машиной с произвольным доступом или машиной Тьюринга , поэтому не существует машины, которая была бы ограничена в вычислительном отношении. Это предложение формальноневозможно доказать, но это общепринято. Говорят, что модель компьютерной системы, а именно язык программирования, «полностью совместима с Тьюрингом», если с ее помощью можно моделировать универсальную машину Тьюринга. Все современные компьютеры «полностью совместимы по Тьюрингу», что означает, что можно найти решение любой проблемы, связанной с принятием решений. Термин « разрешимость» можно описать как вопрос о том, является ли конкретная проблема алгоритмически разрешимой или нет. Так, например, проблема наименьшего общего кратного двух чисел является разрешимой проблемой. Неразрешимой проблемой является, например, вопрос о том, сможет ли компьютер при определенных входных параметрах когда-либо получить результат, известный как проблема остановки.. Теория вычислений исследует, какие машины могут использоваться для выполнения заданной функции. Таким образом , например, функция Аккермана решается не классом программ цикла , а более эффективным классом программ while
