Алгори́тм — совокупность точно заданных правил решения некоторого класса задач или набор инструкций, описывающих порядок действий исполнителя для решения определённой задачи. В старой трактовке вместо слова «порядок» использовалось слово «последовательность», но по мере развития параллельности в работе компьютеров слово «последовательность» стали заменять более общим словом «порядок». Независимые инструкции могут выполняться в произвольном порядке, параллельно, если это позволяют используемые исполнители.
Теория чисел или высшая арифметика — раздел математики, первоначально изучавший свойства целых чисел. В современной теории чисел рассматриваются и другие типы чисел — например, алгебраические и трансцендентные, а также функции различного происхождения, которые связаны с арифметикой целых чисел и их обобщений.
Реку́рсия — определение, описание, изображение какого-либо объекта или процесса внутри самого этого объекта или процесса, то есть ситуация, когда объект является частью самого себя. Термин «рекурсия» используется в различных специальных областях знаний — от лингвистики до логики, но наиболее широкое применение находит в математике и информатике.
Те́зис Чёрча — Тью́ринга — логико-математический принцип, устанавливающий эквивалентность между интуитивным понятием алгоритмической вычислимости и строго формализованными понятиями частично рекурсивной функции и функции, вычислимой на машине Тьюринга. В связи с интуитивностью исходного понятия алгоритмической вычислимости, данный тезис носит характер суждения об этом понятии и его невозможно строго доказать или опровергнуть. Перед точным определением вычислимой функции математики часто использовали неофициальный термин, «эффективно вычислимый» для описания функций, которые можно вычислить с помощью «бумажно-карандашных» методов.
Фракта́л — множество, обладающее свойством самоподобия. В математике под фракталами понимают множества точек в евклидовом пространстве, имеющие дробную метрическую размерность, либо метрическую размерность, отличную от топологической, поэтому их следует отличать от прочих геометрических фигур, ограниченных конечным числом звеньев. Самоподобные фигуры, повторяющиеся конечное число раз, называются предфракталами.
Полнота по Тьюрингу — характеристика исполнителя в теории вычислимости, означающая возможность реализовать на нём любую вычислимую функцию. Другими словами, для каждой вычислимой функции существует вычисляющий её элемент или программа для исполнителя, а все функции, вычисляемые множеством вычислителей, являются вычислимыми функциями.
Теоре́ма — математическое утверждение, истинность которого устанавливается путём доказательства. Доказательства теорем опираются на ранее доказанные теоремы и общепризнанные утверждения (аксиомы).
Теория вычислимости, также известная как теория рекурсивных функций, — это раздел современной математики, лежащий на стыке математической логики, теории алгоритмов и информатики, возникшей в результате изучения понятий вычислимости и невычислимости. Изначально теория была посвящена вычислимым и невычислимым функциям и сравнению различных моделей вычислений. В наши дни поле исследования теории вычислимости расширилось — появляются новые определения понятия вычислимости и идёт слияние с математической логикой, где вместо вычислимости и невычислимости идёт речь о доказуемости и недоказуемости утверждений в рамках каких-либо теорий.
Проблема остановки — одна из проблем в теории алгоритмов, которая может неформально быть поставлена в виде:
- Даны описание процедуры и её начальные входные данные. Требуется определить: завершится ли когда-либо выполнение процедуры с этими данными; либо, что процедура всё время будет работать без остановки.
Конструктивная математика — абстрактная наука о мыслительных конструктивных процессах, человеческой способности осуществлять их, и об их результатах — конструктивных математических объектах. Является результатом развития конструктивного направления в математике — математического мировоззрения, которое в отличие от теоретико-множественного направления считает основной задачей математики исследование конструктивных процессов и конструктивных объектов.
Алгоритмическая разрешимость — свойство формальной теории обладать алгоритмом, определяющим по данной формуле, выводима она из множества аксиом данной теории или нет. Теория называется разрешимой, если такой алгоритм существует, и неразрешимой, в противном случае. Вопрос о выводимости в формальной теории является частным, но вместе с тем важнейшим случаем более общей проблемы разрешимости.
Теорема По́ста — теорема теории вычислимости о рекурсивно перечислимых множествах.
В разделе информатики — алгоритмической теории информации, константа Хайтина или вероятность остановки — вещественное число, которое, неформально говоря, является вероятностью того, что произвольно выбранная программа остановится. Существование таких чисел было продемонстрировано Грегори Хайтином.
Вычисли́мые фу́нкции — множество функций то есть отображения множества натуральных чисел во множество натуральных чисел, в математических обозначениях это 
которые могут быть реализованы некоторым, алгоритмом, описание которого конечно, например, описанием переходов некоторой машиной Тьюринга.
Тео́рия алгори́тмов — раздел математики, изучающий общие свойства и закономерности алгоритмов и разнообразные формальные модели их представления. К задачам теории алгоритмов относятся формальное доказательство алгоритмической неразрешимости задач, асимптотический анализ сложности алгоритмов, классификация алгоритмов в соответствии с классами сложности, разработка критериев сравнительной оценки качества алгоритмов и т. п. Вместе с математической логикой теория алгоритмов образует теоретическую основу вычислительных наук, теории передачи информации, информатики, телекоммуникационных систем и других областей науки и техники.
В математике, логике и информатике рекурсивно перечислимым языком называется тип формального языка, также известный как частично разрешимый, или распознаваемый по Тьюрингу. В иерархии Хомского он известен как язык типа 0. Класс всех рекурсивно перечислимых языков называется RE.
Анато́лий Ива́нович Ма́льцев — советский математик, основоположник сибирской школы алгебры и логики. Академик АН СССР (1958). Лауреат Ленинской премии.
Разреши́мое множество — множество натуральных чисел, для которого существует алгоритм, получающий на вход любое натуральное число и через конечное число шагов завершающийся определением, принадлежит ли оно данному множеству. Другими словами, множество является разрешимым, если его характеристическая функция вычислима. Множество, не являющееся разрешимым, называется неразреши́мым. Также можно говорить о разрешимом множестве, состоящем из любых конструктивных объектов, кодируемых натуральными числами. Любое разрешимое множество является перечислимым и арифметическим. Разрешимые множества соответствуют уровню 
арифметической иерархии.
Интуициони́зм — совокупность философских и математических взглядов, рассматривающих математические суждения с позиций «интуитивной убедительности». Различаются две трактовки интуиционизма: интуитивная убедительность, которая не связана с вопросом существования объектов, и наглядная умственная убедительность.
Альберт Абрамович Мучник — советский и российский математик, работавший в области теории вычислимости и математической логики.