Главная страница Случайная страница КАТЕГОРИИ: АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Определение вычислимой функции ⇐ ПредыдущаяСтр 3 из 3
Пусть функция определена на подмножестве множества всех наборов чисел из расширенного натурального ряда и принимающая значения также из .Такого рода функции называются частичными функциями счетнозначной логики. Обозначим через множество всех частичных функций счетнозначной логики. Функция называется вычислимой, если существует машина Тьюринга такая, что: 1) при машина , будучи применена к основному коду и находясь в начальном состоянии над его левой единицей, останавливается и в заключительном состоянии на ленте выдает код для ; 2) при машина , будучи применена к основному коду и находясь в начальном состоянии над его левой единицей, либо не останавливается, либо останавливается, но при этом запись на ленте отлична от кода для . Обозначим через класс всех вычислимых функций. Очевидно, . Машина Тьюринга реализует (вычисляет) функцию правильным образом, если: 1) при машина , будучи применена к основному коду и находясь в начальном состоянии над его левой единицей, останавливается и в заключительном состоянии на ленте выдает код для ; при этом останов происходит над левой единицей кода для ; 2) при машина , будучи применена к основному коду и находясь в начальном состоянии над его левой единицей, либо не останавливается. Лемма. Если – вычислимая функция, то существует машина Тьюринга, которая вычисляет ее правильным образом.
|