Алгори́тм — совокупность точно заданных правил решения некоторого класса задач или набор инструкций, описывающих порядок действий исполнителя для решения определённой задачи. В старой трактовке вместо слова «порядок» использовалось слово «последовательность», но по мере развития параллельности в работе компьютеров слово «последовательность» стали заменять более общим словом «порядок». Независимые инструкции могут выполняться в произвольном порядке, параллельно, если это позволяют используемые исполнители.
Нау́ка — деятельность, направленная на выработку и систематизацию объективных знаний о действительности.
Програ́ммное обеспе́чение (ПО) — программа или множество программ, используемых для управления компьютером.
А́лан Мэ́тисон Тью́ринг — британский математик, логик, криптограф, оказавший существенное влияние на развитие информатики. Офицер ордена Британской империи, член Лондонского королевского общества (1951).
Те́зис Чёрча — Тью́ринга — логико-математический принцип, устанавливающий эквивалентность между интуитивным понятием алгоритмической вычислимости и строго формализованными понятиями частично рекурсивной функции и функции, вычислимой на машине Тьюринга. В связи с интуитивностью исходного понятия алгоритмической вычислимости, данный тезис носит характер суждения об этом понятии и его невозможно строго доказать или опровергнуть. Перед точным определением вычислимой функции математики часто использовали неофициальный термин, «эффективно вычислимый» для описания функций, которые можно вычислить с помощью «бумажно-карандашных» методов.
Клод Э́лвуд Ше́ннон — американский инженер, криптоаналитик и математик. Считается «отцом информационного века».
Теорема Гёделя о неполноте и вторая теорема Гёделя — две теоремы математической логики о принципиальных ограничениях формальной арифметики и, как следствие, всякой формальной системы, в которой можно определить основные арифметические понятия: натуральные числа, 0, 1, сложение и умножение.
Теория вычислимости, также известная как теория рекурсивных функций, — это раздел современной математики, лежащий на стыке математической логики, теории алгоритмов и информатики, возникшей в результате изучения понятий вычислимости и невычислимости. Изначально теория была посвящена вычислимым и невычислимым функциям и сравнению различных моделей вычислений. В наши дни поле исследования теории вычислимости расширилось — появляются новые определения понятия вычислимости и идёт слияние с математической логикой, где вместо вычислимости и невычислимости идёт речь о доказуемости и недоказуемости утверждений в рамках каких-либо теорий.
Проблема остановки — одна из проблем в теории алгоритмов, которая может неформально быть поставлена в виде:
- Даны описание процедуры и её начальные входные данные. Требуется определить: завершится ли когда-либо выполнение процедуры с этими данными; либо, что процедура всё время будет работать без остановки.
Алонзо Чёрч — американский математик и логик, внесший значительный вклад в основы информатики.
Алгоритмическая разрешимость — свойство формальной теории обладать алгоритмом, определяющим по данной формуле, выводима она из множества аксиом данной теории или нет. Теория называется разрешимой, если такой алгоритм существует, и неразрешимой, в противном случае. Вопрос о выводимости в формальной теории является частным, но вместе с тем важнейшим случаем более общей проблемы разрешимости.
Тео́рия алгори́тмов — раздел математики, изучающий общие свойства и закономерности алгоритмов и разнообразные формальные модели их представления. К задачам теории алгоритмов относятся формальное доказательство алгоритмической неразрешимости задач, асимптотический анализ сложности алгоритмов, классификация алгоритмов в соответствии с классами сложности, разработка критериев сравнительной оценки качества алгоритмов и т. п. Вместе с математической логикой теория алгоритмов образует теоретическую основу вычислительных наук, теории передачи информации, информатики, телекоммуникационных систем и других областей науки и техники.
Квантовая машина Тьюринга — абстрактная машина, используемая для моделирования квантового компьютера; простая модель, которая, в то же время, может описать любые квантовые вычисления: любой квантовый алгоритм может быть формально описан как некоторая квантовая машина Тьюринга. Впервые построена в 1985 году Дэвидом Дойчем, обратившим внимание на аналогию между квантовыми вентилями и логическими вентилями в цифровых схемах.
Теоре́ма Чёрча — Тью́ринга — утверждение об отсутствии алгоритма, решающего проблему разрешения. Используется при доказательстве неразрешимости арифметики натуральных чисел. Впервые была сформулирована и доказана в 1936 году Алонзо Чёрчем ; в том же году, но несколько позже этот результат независимо получил Алан Тьюринг.
Сверхсоставное число — натуральное число с бо́льшим числом делителей, чем любое меньшее натуральное число.
Непредикати́вность определения в математике и логике, нестрого говоря, означает, что осмысленность определения предполагает наличие определяемого объекта. Пример: объект 
определяется как такой элемент некоторого множества, который удовлетворяет определённому отношению между ним и всеми элементами этого множества. В некоторых случаях непредикативное определение может привести к недоразумениям или даже противоречиям. Противоположное по смыслу понятие — предикативность.
Группа Рудвалиса Ru — это спорадическая простая группа порядка
- 214 · 33 · 53 · 7 · 13 · 29
- = 145926144000
- ≈ 1⋅1011.
Филипп Холл — английский математик. Член Лондонского королевского общества, профессор Кембриджского университета. Наиболее известен работами по теории групп, в особенности по конечным группам и разрешимым группам. В течение многих лет Холл был единственным алгебраистом, работающим в Англии.
Рубен Луис Гудстейн — английский математик. Серьёзно интересовался философией, преподавал математику.
