Разрешимое множество — В теории множеств, теории алгоритмов и математической логике, множество натуральных чисел называется разрешимым или рекурсивным, если существует алгоритм, который, получив на вход любое натуральное число, через конечное число шагов завершается и… … Википедия
Разрешимое множество — в логике, множество, расположенное в некоторой совокупности конструктивных объектов (См. Конструктивные объекты) (т. е. множество, составленное из каких то объектов этой совокупности), для которого существует Алгоритм, разрешающий это… … Большая советская энциклопедия
РАЗРЕШИМОЕ И ПЕРЕЧИСЛИМОЕ МНОЖЕСТВА — осн. понятия теории алгоритмов и теории рекурсивных функций (и предикатов). (Определение этих понятий на основе понятия алгоритма см. в ст. Алгоритм, раздел Основные понятия теории А.) Простейшим примером разрешимого множества может служить… … Философская энциклопедия
ПЕРЕЧИСЛИМОЕ МНОЖЕСТВО — множество, возникающее в результате развертывания какого либо конструктивного порождающего процесса. Такой процесс можно мыслить как процесс вычисления значений нек рого алгоритма с исходными данными в виде натуральных чисел, и потому, напр.,… … Математическая энциклопедия
Перечислимое множество — Не следует путать с счётным множеством. В теории множеств, теории алгоритмов и математической логике, перечислимое множество (эффективно перечислимое, рекурсивно перечислимое, полуразрешимое множество[1]) множество конструктивных объектов… … Википедия
Арифметическое множество — В теории множеств и математической логике, множество натуральных чисел называется арифметическим, если оно может быть определено формулой в языке арифметики первого порядка, то есть если существует такая формула с одной свободной переменной что… … Википедия
ПРОСТОЕ МНОЖЕСТВО — рекурсивно перечислимое множество натуральных чисел, дополнение к рого есть иммунное множество. П. м. являются промежуточными в смысле так наз. m сводимости (см. Рекурсивная теория множеств).между разрешимыми множествами и творческими… … Математическая энциклопедия
ДИОФАНТОВО МНОЖЕСТВО — множество состоящее из упорядоченных наборов из пцелых (целых неотрицательных, целых положительных) чисел, для к рого можно указать диофантово уравнение зависящее от ппараметров а 1, ..., а п, допустимыми значениями к рых являются целые… … Математическая энциклопедия
АЛГОРИТМ — [от algorithm!; algorismus, первоначально лат. транслитерация имени ср. азиат. учёного 9 в. Хорезми (Мухаммед бен Муса аль Хорезми)], программа, определяющая способ поведения (вычисления); система правил (предписаний) для эффективного… … Философская энциклопедия
Алгоритмов теория — раздел математики, изучающий общие свойства Алгоритмов. Содержательные явления, приведшие к образованию понятия «алгоритм», прослеживаются в математике в течение всего времени её существования. Однако само это понятие сформировалось лишь… … Большая советская энциклопедия
В этом случае f и представляет собой алгоритм, проверяющий принадлежность к Мнатуральных чисел. В самом деле, 
равносильно тому, что f(n)=0. Р. м. натуральных чисел часто наз. также о б щ е р е-к у р с и в н ы м, или р е к у р с и в н ы м, м н о ж ес т в о м.