Часовой пояс: UTC + 3 часа [ Летнее время ]

Машины Тьюринга и тезис
Онлайн-сервисы Нахождение НОД и НОК Разложение числа на простые множители Сравнения по модулю Операции над множествами Операции над векторами Разложение вектора по базису. Доказательство, что векторы образуют базис Чертёж треугольника по координатам вершин Решение треугольника Решение Пирамиды Построение Пирамиды по координатам вершин Чертёж многоугольника по координатам вершин Решение систем методом Крамера и Матричным Онлайн построение графика кривой 2-го порядка Определение вида кривой или поверхности 2-го порядка по инвариантам МНК и регрессионный анализ Онлайн + графики Онлайн число, сумма и дата прописью Алгоритмы JavaScript Алгоритмы поиска Алгоритмы сортировки Уникальные элементы массива Объединение, пересечение и разность массивов НОД и НОК Операции над матрицами Дата прописью Введение в анализ Функции: понятие, определение, графики Непрерывность функции Исследование функции и построение графика Теория множеств Множества: понятие, определение, примеры Точечные множества Замкнутые и открытые множества Мера множества Группы, кольца, поля в математике Поле комплексных чисел Кольцо многочленов Основная теорема алгебры и ее следствия Математическая логика Алгебра высказываний Аксиоматика и логические рассуждения Методы доказательств теорем Алгебра высказываний и операции над ними Формулы алгебры высказываний Тавтологии алгебры высказываний Логическая равносильность формул Нормальные формы для формул высказываний Логическое следование формул Приложение алгебры высказываний для теорем Дедуктивные и индуктивные умозаключения Решение логических задач Принцип полной дизъюнкции Булевы функции Множества, отношения и функции в логике Булевы функции от одного и двух аргументов Булевы функции от n аргументов Системы булевых функций Применение булевых функций к релейно-контактным схемам Релейно-контактные схемы в ЭВМ Практическое применение булевых функций Теория формального Формализованное исчисление высказываний Полнота и другие свойства формализованного исчисления высказываний Независимость системы аксиом формализованного исчисления высказываний Логика предикатов Логика предикатов Логические операции над предикатами Кванторные операции над предикатами Формулы логики предикатов Тавтологии логики предикатов Преобразования формул и следование их предикатов Проблемы разрешения для общезначимости и выполнимости формул Применение логики предикатов в математике Строение математических теорем Аристотелева силлогистика и методы рассуждений Принцип полной дизъюнкции в предикатной форме Метод полной математической индукции Необходимые и достаточные условия Логика предикатов и алгебра множеств Формализованное исчисление предикатов Неформальные и формаль- ные аксиоматические теории Неформальные аксиоматические теории Свойства аксиоматических теорий Формальные аксиоматические теории Формализация теории аристотелевых силлогизмов Свойства формализованного исчисления предикатов Формальные теории первого порядка Формализация математической теории Теория алгоритмов Интуитивное представление об алгоритмах Машины Тьюринга и тезис Рекурсивные функции Нормальные алгоритмы Маркова Разрешимость и перечислимость множеств Неразрешимые алгоритмические проблемы Теорема Гёделя о неполноте формальной арифметики Математическая логика и компьютеры Математическая логика и языки программирования Применение компьютеров для доказательства теорем математической логики Математическая логика и логическое программирование Математическая логика и информатика Математическая логика и искусственный интеллект Дискретная математика Множества и отношения Теория множеств: понятия и определения Операции над множествами Кортеж и декартово произведение множеств Соответствия и бинарные отношения на множествах Операции над соответствиями на множествах Семейства множеств Специальные свойства бинарных отношений Отношения эквивалентности на множестве Упорядоченные множества Теорема о неподвижной точке Мощность множества Парадокс Рассела Метод характеристических функций Группы и кольца Алгебраические структуры и операции Группоиды, полугруппы, группы Кольца, тела, поля Области целостности в теории колец Модули и линейные пространства Подгруппы и подкольца Теорема Лагранжа о порядке конечной группы Гомоморфизмы групп и нормальные делители Гомоморфизмы и изоморфизмы колец Алгебра кватернионов Полукольца и булевы алгебры Полукольца: определение, аксиомы, примеры Замкнутые полукольца Полукольца и системы линейных уравнений Булевы алгебры и полукольца Решетки и полурешетки Алгебраические системы Алгебраические системы: модели и алгебры Подсистемы алгебраических систем Конгруэнции и фактор-системы Гомоморфизмы алгебраических систем Прямые произведения алгебраических систем Конечные булевы алгебры Многосортные алгебры Теория графов Теория графов: основные понятия и определения Способы представления графов Неориентированные и ориентированные деревья Остовное дерево и алгоритм Краскала Методы систематического обхода вершин графа Алгоритмы поиска в глубину и ширину в графах Задача о путях во взвешенных ориентированных графах Изоморфизм, гомоморфизм и автоморфизм графов Топологическая сортировка вершин графа Элементы цикломатики в теории графов Булева алгебра и функции Булевы функции и булев куб Таблицы булевых функций и булев оператор Равенство булевых функций. Фиктивные переменные Формулы и суперпозиции булевых функций Дизъюнктивные и конъюнктивные нормальные формы Построение минимальных ДНФ Теорема Поста и классы Критерий Поста Схемы из функциональных элементов Конечные автоматы и регулярные языки Конечные автоматы и регулярные языки Алфавит, слово, язык в программировании Порождающие грамматики (грамматики Хомского) Классификация грамматик и языков Регулярные языки и регулярные выражения Конечные автоматы Допустимость языка конечным автоматом Теорема Клини Детерминизация конечных автоматов Минимизация конечных автоматов Лемма о разрастании для регулярных языков Обоснование алгоритма детерминизации автоматов Конечные автоматы с выходом Морфизмы и конечные подстановки Машины Тьюринга Контекстно-свободные языки Контекстно-свободные языки и грамматики Приведенная форма КС-грамматики Лемма о разрастании для КС-языков Магазинные автоматы (автомат с магазинной памятью) Алгоритм построения МП-автомата по КС-грамматике Алгоритм построения КС-грамматики по МП-автомату Алгебраические свойства КС-языков Основное свойство суперпозиции КС-языков Пересечение контекстно-свободных языков Методы синтаксического анализа КС-языков Восходящий синтаксический анализ и LR(k)-грамматики Семантика формальных языков Принцип индукции по неподвижной точке Графовое представление МП-автоматов Интегральное исчисление Неопределённый и определённый Неопределенный и определенный интегралы Свойства интегралов Интегрирование по частям Интегрирование методом замены переменной Интегрирование различных рациональных функций Интегрирование различных иррациональных функций Интегрирование различных тригонометрических функций Определенный интеграл и его основные свойства Необходимое и достаточное условие интегрируемости Теоремы существования первообразной Свойства определенных интегралов Несобственные интегралы Интегральное определение логарифмической функции Приложения интегралов Вычисление площадей плоских фигур Площади фигур в различных координатах Вычисление объемов тел с помощью интегралов Объём тела вращения Вычисление длин дуг кривых Формулы длины дуги регулярной кривой Кривизна плоской кривой Площадь поверхности вращения тела Интегралы в физике Статические моменты и координаты центра тяжести Теоремы Гульдина–Паппа Вычисление моментов инерции Другие приложения интегралов в физике Основные интегралы Интеграл Ньютона-Лейбница Интеграл Римана Интеграл Лебега Вариационное исчисление Примеры вариационных задач Дифференциальное уравнение Эйлера Функционалы, зависящие от нескольких функций Задача о минимуме кратного интеграла Финансовый анализ Анализ эффективности Критерии и показатели эффективности предприятия Методы анализа эффективности деятельности Факторный анализ прибыли от операционной деятельности Анализ безубыточности предприятия Операционный рычаг и эффект финансового рычага Анализ и оценка состава, структуры и динамики доходов и расходов Анализ рентабельности и резервов устойчивого роста капитала Анализ распределения прибыли предприятия Анализ и оценка чувствительности показателей эффективности Анализ устойчивости Финансовая устойчивость и долгосрочная платежеспособность Характеристика типов финансовой устойчивости Рыночная активность Финансовый анализ рыночной активности Методика анализа рыночной активности Анализ и оценка дивидендного дохода на одну акцию Инвестиционная деятельность Инвестиции: экономическая сущность и классификация Государственное регулирование инвестиционной деятельности Источники финансовых ресурсов на капитальные вложения Инвестиции в основные фонды Оценка состояния основных фондов Амортизация основных фондов Капитальное строительство в инвестиционном процессе Планирование инвестиций в форме капитальных вложений Экономическая эффективность инвестиций Финансирование капитальных вложений Кредитование капитальных вложений Кредитоспособность Финансирование и кредитование затрат Финансирование и кредитование инвестиционной деятельности потребительской кооперации Финансирование и кредитование капитальных вложений потребительской кооперации Инвестиционное строительное проектирование Анализ инвестиций Инвестиции и инвестиционная деятельность предприятия Задачи финансового анализа инвестиций предприятия Учет фактора времени в инвестиционной деятельности Аннуитет и финансовая рента в инвестициях Учет фактора инфляции при инвестировании Оценка фактора риска инвестиционного проекта Методы оценки эффективности инвестиций Показатели эффективности инвестиционного проекта Стоимость компании Концепция построения международных стандартов финансовой отчетности (МСФО) Экономическое содержание международных стандартов финансовой отчётности Цели и принципы оценки стоимости акций и активов компании Оценка акций и активов предприятия по справедливой стоимости Методы оценки справедливой стоимости акций предприятия Затратный подход к оценки стоимости компаний и акций Сравнительный подход к оценки стоимости предприятий и акций Доходный подход к оценке стоимости компании и акций Выбор ставки дисконтирования при инвестировании в акции Метод капитализации прибыли Сравнение подходов к оценке стоимости компаний и пакетов акций Форвардные контракты Форвардный контракт и цена Форвардная цена акции на бирже Цена форвардного контракта инвестора Форвардная цена акции с учетом величины дивиденда Форвардная цена акции с учетом ставки дивиденда Форвардная цена валюты на рынке форекс Форвардный валютный курс и инфляция на рынке Форвардная цена товара и спотовый рынок Форвардная цена при различии ставок по кредитам и депозитам Синтетический форвардный контракт на акции и валюту Теория вероятностей Основные понятия теории вероятностей Зависимые и независимые случайные события Повторные независимые испытания Формула Бернулли Одномерные случайные величины Многомерные случайные величины Функции случайных величин Законы распределения целочисленных случайных величин Законы распределения непрерывных случайных величин Предельные теоремы теории вероятностей Закон больших чисел и предельные теоремы Вероятностные закономерности Математическая статистика Элементы математической статистики Выборочный метод Оценки параметров генеральной совокупности Статистические гипотезы Критерии согласия Теоретические и эмпирические частоты Теория очередей (СМО) Определение системы массового обслуживания Уравнения Колмогорова Предельные вероятности состояний Определение СМО с отказами Определение СМО с ожиданием (очередью) Аналитическая геометрия Векторная алгебра Метрические понятия и аксиомы геометрии Равенство и подобие геометрических фигур Бинарные отношения Вектор, его направление и длина Линейные операции над векторами Линейная зависимость и независимость векторов Отношение коллинеарных векторов Проекции векторов на прямую и на плоскость Угол между векторами Ортогональные проекции векторов Координата вектора на прямой и базис Координаты вектора на плоскости и базис Координаты вектора в пространстве и базис Операции над векторами в координатной форме Ортогональный и ортонормированный базисы Cкалярное произведение векторов и его свойства Выражение скалярного произведения через координаты векторов Векторное произведение векторов и его свойства Смешанное произведение векторов и его свойства Ориентированные площади и объемы Двойное векторное произведение и его свойства Применение векторов в задачах на аффинные свойства фигур Применение произведений векторов при решении геометрических задач Применение векторной алгебры в механике Системы координат Прямоугольные координаты Преобразования прямоугольных координат Полярная система координат Цилиндрическая система координат Сферические координаты Аффинные координаты Аффинные преобразования координат Аффинные преобразования плоскости Примеры аффинных преобразований плоскости Аффинные преобразования пространства Многомерное координатное пространство Линейные и аффинные подпространства Скалярное произведение n-мерных векторов Преобразования систем координат Геометрия на плоскости Алгебраические линии на плоскости Общие уравнения геометрических мест точек Алгебраические уравнения линий на плоскости Уравнения прямой, проходящей через точку перпендикулярно вектору Уравнения прямой, проходящей через точку коллинеарно вектору Уравнения прямой, проходящей через две точки Уравнения прямой с угловым коэффициентом Взаимное расположение прямых Примеры задач с прямыми на плоскости Системы неравенств с двумя неизвестными Системы линейных уравнений с двумя неизвестными Линии 2-го порядка Канонические уравнения линий второго порядка Порядок приведения уравнения линии к каноническому виду Эллипс Гипербола Парабола Квадратичные неравенства с двумя неизвестными Применение линий 1-го и 2-го порядков в задачах на экстремум функций Инварианты линий Классификация линий 2-го порядка по инвариантам Приведение уравнения линии к каноническому виду по инвариантам Геометрия в пространстве Способы задания ГМТ в пространстве Алгебраические уравнения поверхностей Уравнения плоскости, проходящей через точку перпендикулярно вектору Уравнения плоскости, компланарной двум неколлинеарным векторам Уравнения плоскости, проходящей через три точки Взаимное расположение плоскостей Типовые задачи с плоскостями Уравнения прямых в пространстве Взаимное расположение прямых в пространстве Типовые задачи с прямыми в пространстве Поверхности 2-го порядка Канонические уравнения поверхностей Порядок приведения уравнения поверхности к каноническому виду Поверхности второго порядка Эллипсоиды Гиперболоиды Конусы Параболоиды Применение поверхностей 1-го и 2-го порядков в задачах на экстремум функций Инварианты поверхностей Классификация поверхностей 2-го порядка по инвариантам Квадратичные неравенства с тремя неизвестными Приведение уравнения поверхности к канониче-скому виду по инвариантам Линейная алгебра Матрицы и операции Линейные операции над матрицами Умножение матриц Возведение матриц в степень Многочлены от матриц Транспонирование и сопряжение матриц Блочные матрицы Произведение и сумма матриц Кронекера Метод Гаусса приведения матрицы к ступенчатому виду Элементарные преобразования матриц Определители Определители матриц и их основные свойства Формула полного разложения определителя Формула Лапласа полного разложения определителя Определитель произведения матриц Методы вычисления определителей Ранг матрицы Линейная зависимость и линейная независимость строк (столбцов) матрицы Ранг матрицы и базисный минор матрицы Методы вычисления ранга матрицы Ранг системы столбцов (строк) Обратная матрица Обратные матрицы и их свойства Ортогональные и унитарные матрицы Способы нахождения обратной матрицы Матричные уравнения Односторонние обратные матрицы Скелетное разложение матрицы Полуобратная матрица Псевдообратная матрица Системы уравнений Системы линейных алгебраических уравнений Метод Гаусса решения систем линейных уравнений Структура общего решения системы уравнений Решение систем с помощью полуобратных матриц Псевдорешения системы линейных уравнений Функциональные матрицы Функциональные матрицы скалярного аргумента Производные матриц по векторному аргументу Линейные и квадратичные формы и их преобразования Приведение форм к каноническому виду Закон инерции вещественных квадратичных форм Знакоопределенность форм вещественных квадратичных Формы и исследование функций на экстремум Многочленные матрицы Многочленные матрицы (лямбда-матрицы) Операции над лямбда-матрицами Простые преобразования многочленных матриц Инвариантные множители многочленной матрицы Функции от матриц Собственные векторы и значения матрицы Подобие числовых матриц Характеристический многочлен матрицы Минимальный многочлен матрицы Теорема Гамильтона-Кэли Жорданова форма матрицы Приведение матрицы к жордановой форме Многочлены от матриц Применение многочленов от матриц Функции от матриц Линейные пространства Линейные пространства: определение и примеры Линейная зависимость и независимость n-мерных векторов Размерность и базис линейного пространства Преобразования координат в линейном пространстве Изоморфизм линейных пространств Подпространства Подпространства линейного пространства Пересечение и сумма подпространств Способы описания подпространств Нахождение дополнения и суммы подпространств Нахождение пересечения подпространств Линейные отображения Линейные многообразия Линейные отображения Матрица линейного отображения Ядро и образ линейного отображения Линейные операторы Линейные операторы (преобразования) Инвариантные подпространства Собственные векторы и значения оператора Свойства собственных векторов операторов Канонический вид линейного оператора Методика приведения линейного преобразования к каноническому виду Евклидовы пространства Евклидовы пространства Ортогональные векторы евклидова пространства Ортогональный базис евклидова пространства Ортонормированный базис евклидова пространства Ортогональные дополнения в евклидовом пространстве Задача о перпендикуляре Матрица и определитель Грама и его свойства Линейные преобразования евклидовых пространств Канонический вид ортогонального оператора евклидова пространства Сопряженные операторы евклидова пространства Самосопряженные операторы евклидова пространства Приведение квадратичной формы к главным осям Унитарные пространства и их линейные преобразования Комплексный анализ Комплексные числа Комплексные числа в алгебраической форме Комплексные числа в тригонометрической и показательной формах Множества на комплексной плоскости Последовательности и ряды комплексных чисел Комплексные функции Функции комплексного переменного. Предел, непрерывность и производная Элементарные функции комплексного переменного Дифференцирование функций комплексного переменного Аналитические функции и их свойства Конформные отображения и их свойства Интегрирование функций комплексного переменного Функциональные ряды в комплексной области Функциональные ряды и последовательности Степенные ряды и их свойства Разложение функций в степенные ряды Нули аналитических функций Ряд Лорана и разложение функций по целым степеням Особые точки, Вычеты Изолированные особые точки функций и полюсы Вычеты и их применение Вычисление интегралов с помощью вычетов Вычеты и расположение нулей многочлена Операционное исчисление Преобразование Лапласа и его свойства Решение ДУ операционным методом Анализ выходных процессов линейных стационарных систем Z-преобразование и его свойства Дифференциальные уравнения ДУ первого порядка Основные понятия и определения ДУ Метод изоклин для ДУ 1-го порядка Метод последовательных приближений ДУ с разделяющимися переменными Однородные ДУ Линейные ДУ 1-го порядка Дифференциальное уравнение Бернулли ДУ в полных дифференциалах Интегрирующий множитель ДУ, не разрешенные относительно производной Дифференциальное уравнение Риккати Составление ДУ семейств линий Задачи на траектории Особые решения ДУ ДУ высших порядков Понятия и определения ДУ высших порядков ДУ, допускающие понижение порядка Линейная независимость функций Определители Вронского и Грама Однородные и неоднородные дифференциальные уравнения Задача Коши и Уравнение Эйлера Линейные ДУ с переменными коэффициентами Метод Лагранжа решения ДУ Краевые задачи для ДУ высших порядков Разложение решения ДУ в степенной ряд Разложение решения ДУ в обобщенный степенной ряд Нахождение периодических решений ДУ Асимптотическое интегрирование ДУ Системы ДУ Системы ДУ: понятия и определения Сведение системы ДУ к одному уравнению Нахождение интегрируемых комбинаций Интегрирование однородных линейных систем ДУ Методы интегрирования неоднородных систем ДУ Преобразование Лапласа и решение ДУ и систем Теория устойчивости Устойчивость решений ДУ по Ляпунову Простейшие типы точек покоя Метод функций Ляпунова Устойчивость решений ДУ по первому приближению Критерии устойчивости Рауса–Гурвица и Михайлова ДУ с малым параметром при производной Численные методы Методы алгебры Численные методы линейной алгебры Численные методы решения СЛАУ Итерационный метод Шульца обратной матрицы Методы решения задач о собственных значениях и векторах матрицы Методы решения нелинейных уравнений Методы решения систем нелинейных уравнений Методы теории приближений Методы приближения сеточных функций Методы функциональной интерполяции Методы интегрально-дифференциальной интерполяции Методы интегрального сглаживания Методы интерполяции и сглаживания сплайнами Методы численного дифференцирования и интегрирования Методы численного дифференцирования Методы численного интегрирования Методы решения обыкновенных ДУ Численные методы решения задачи Коши Разностные схемы для решения задачи Коши Составные схемы для решения задачи Коши Экстраполяционные методы решения задачи Коши Непрерывно-дискретные методы решения задачи Коши Численные методы решения краевых задач Методы решения ДУ в частных производных Численные методы решения уравнений математической физики с двумя переменными Принципы построения разностных схем для уравнений в частных производных Разностные схемы решения уравнений в частных производных 1-го порядка Разностные схемы решения уравнений в частных производных 2-го порядка Численные методы решения уравнений в частных производных Численные методы решения уравнений математической физики с тремя переменными	Машины Тьюринга и тезис Введение понятия машины Тьюринга явилось одной из первых и весьма удачных попыток дать точный математический эквивалент для общего интуитивного представления об алгоритме. Это понятие названо по имени английского математика, сформулировавшего его в 1937 г., за 9 лет до появления первой электронно-вычислительной машины. Определение машины Тьюринга Машина Тьюринга есть математическая (воображаемая) машина, а не машина физическая. Она есть такой же математический объект, как функция, производная, интеграл, группа и т.д. И так же как и другие математические понятия, понятие машины Тьюринга отражает объективную реальность, моделирует некие реальные процессы. Именно Тьюринг предпринял попытку смоделировать действия математика (или другого человека), осуществляющего некую умственную созидательную деятельность. Такой человек, находясь в определенном "умонастроении" ("состоянии"), просматривает некоторый текст. Затем он вносит в этот текст какие-то изменения, проникается новым "умонастроением" и переходит к просмотру последующих записей. Машина Тьюринга действует примерно также. Ее удобно представлять в виде автоматически работающего устройства. В каждый дискретный момент времени устройство, находясь в некотором состоянии, обозревает содержимое одной ячейки протягиваемой через устройство ленты и делает шаг, заключающийся в том, что устройство переходит в новое состояние, изменяет (или оставляет без изменения) содержимое обозреваемой ячейки и переходит к обозрению следующей ячейки — справа или слева. Причем шаг осуществляется на основании предписанной команды. Совокупность всех команд представляет собой программу машины Тьюринга. Опишем теперь машину Тьюринга $\Theta$ более тщательно. Машина $\Theta$ располагает конечным числом знаков (символов, букв), образующих так называемый внешний алфавит $A=\{a_0,a_1,\ldots,a_n\}$ . В каждую ячейку обозреваемой ленты в каждый дискретный момент времени может быть записан только один символ из алфавита $A$ . Ради единообразия удобно считать, что среди букв внешнего алфавита $A$ имеется "пустая буква", и именно она записана в пустую ячейку ленты. Условимся, что "пустой буквой" или символом пустой ячейки является буква $a_0$ . Лента предполагается неограниченной в обе стороны, но в каждый момент времени на ней записано конечное число непустых букв. Далее, в каждый момент времени машина $\Theta$ способна находиться в одном состоянии из конечного числа внутренних состояний, совокупность которых $Q=\{q_0,q_1,\ldots,q_m\}$ . Среди состояний выделяются два — начальное $q_1$ и заключительное (или состояние остановки) $q_0$ . Находясь в состоянии $q_1$ машина начинает работать. Попав в состояние $q_0$ , машина останавливается. Работа машины $\Theta$ определяется программой (функциональной схемой). Программа состоит из команд. Каждая команда $T(i,j)$ $(i=1,2,\ldots,m;\, j=0,1,\ldots,n)$ представляет собой выражение одного из следующих видов: $q_ia_j\to q_ka_lC;\quad q_ia_j\to q_ka_l\Pi;\quad q_ia_j\to q_ka_lL,$ (32.1) где $0 \leqslant k \leqslant m,~ 0 \leqslant l \leqslant n$ . В выражениях первого вида символ $C$ будем часто опускать. Как же работает машина Тьюринга? Находясь в какой-либо момент времени в незаключительном состоянии (т. е. в состоянии, отличном от $q_0$ ), машина совершает шаг, который полностью определяется ее текущим состоянием $q_i$ и символом $a_j$ , воспринимаемым ею в данный момент на ленте. При этом содержание шага регламентировано соответствующей командой $T(i,j)\colon q_ia_j\to q_ka_iX$ , где $X\in\{C,\Pi,L\}$ . Шаг заключается в том, что: 1) содержимое $a_j$ обозреваемой на ленте ячейки стирается и на его место записывается символ $a_i$ (который может совпадать с $a_j$ ); 2) машина переходит в новое состояние $q_k$ (оно также может совпадать с предыдущим состоянием $q_i$ ); 3) машина переходит к обозрению следующей правой ячейки от той, которая обозревалась только что, если $X=\Pi$ , или к обозрению следующей левой ячейки, если $X=L$ , или же продолжает обозревать ту же ячейку ленты, если $X=C$ . В следующий момент времени (если $q_k\ne q_0$ ) машина делает шаг, регламентированный командой $T(k,l)\colon q_ka_i\to q_ra_sX$ и т.д. Поскольку работа машины, по условию, полностью определяется ее состоянием $q_i$ в данный момент и содержимым $a_j$ обозреваемой в этот момент ячейки, то для каждых $q_i$ и $a_j~(i=1,2,\ldots,m;\, j=0,1,\ldots,n)$ программа машины должна содержать одну и только одну команду, начинающуюся символами $q_ia_j$ . Поэтому программа машины Тьюринга с внешним алфавитом $A=\{a_0,a_1,\ldots,a_n\}$ и алфавитом внутренних состояний $Q=\{q_0,q_1,\ldots,q_m\}$ содержит $m(n+1)$ команд. Словом в алфавите $A$ или в алфавите $Q$ , или в алфавите $A\cup Q$ называется любая последовательность букв соответствующего алфавита. Под k-й конфигурацией будем понимать изображение ленты машины с информацией, сложившейся на ней к началу k-то шага (или слово в алфавите $A$ , записанное на ленту к началу k-ro шага), с указанием того, какая ячейка обозревается в этот шаг и в каком состоянии находится машина. Имеют смысл лишь конечные конфигурации, т.е. такие, в которых все ячейки ленты, за исключением, быть может, конечного числа, пусты. Конфигурация называется заключительной, если состояние, в котором при этом находится машина, заключительное. Если выбрать какую-либо незаключительную конфигурацию машины Тьюринга в качестве исходной, то работа машины будет состоять в том, чтобы последовательно (шаг за шагом) преобразовывать исходную конфигурацию в соответствии с программой машины до тех пор, пока не будет достигнута заключительная конфигурация. После этого работа машины Тьюринга считается закончившейся, а результатом работы считается достигнутая заключительная конфигурация. Будем говорить, что непустое слово а в алфавите $A\setminus\{a_0\}= \{a_1,\ldots,a_n\}$ воспринимается машиной в стандартном положении, если оно записано в последовательных ячейках ленты, все другие ячейки пусты, и машина обозревает крайнюю справа ячейку из тех, в которых записано слово $\alpha$ . Стандартное положение называется начальным (заключительным), если машина, воспринимающая слово в стандартном положении, находится в начальном состоянии $q_1$ (соответственно в состоянии остановки $q_0$ ). Наконец, будем говорить, что слово $\alpha$ перерабатывается машиной в слово $\beta$ , если от слова $\alpha$ , воспринимаемого в начальном стандартном положении, машина после выполнения конечного числа команд приходит к слову $\beta$ , воспринимаемому в положении остановки. Применение машин Тьюринга к словам Проиллюстрируем на примерах все введенные понятия, связанные с машинами Тьюринга. Пример 32.1. Дана машина Тьюринга с внешним алфавитом $A=\{0;1\}$ (здесь 0 — символ пустой ячейки), алфавитом внутренних состояний $Q=\{q_0,q_1,q_2\}$ и со следующей функциональной схемой (программой): $q_10\to q_2o\Pi;\quad q_20\to q_01;\quad q_11\to q_11\Pi;\quad q_21\to q_21\Pi.$ Посмотрим, в какое слово переработает эта машина слово 101, исходя из стандартного начального положения. Будем последовательно выписывать конфигурации машины при переработке ею этого слова. Имеем стандартное начальное положение: $\begin{array}{cc} \begin{matrix}{}\\(1)\end{matrix}&\qquad \begin{aligned}&\qquad\qquad\qquad\,~~ q_1\\ &\begin{array}{c\|c\|c\|c\|c\|c\|c\|c\|c}\hline \phantom{1}&\phantom{1}&1&0&1&\phantom{1}&\phantom{1}&\phantom{1}&\phantom{1} \\\hline \end{array} \end{aligned} \end{array}$ На первом шаге действует команда: $q_11\to q_11\Pi$ . В результате на машине создается следующая конфигурация: $\begin{array}{cc} \begin{matrix}{}\\(2)\end{matrix}&\qquad \begin{aligned}&\qquad\qquad\qquad\qquad~ q_1\\ &\begin{array}{c\|c\|c\|c\|c\|c\|c\|c\|c}\hline \phantom{1}&\phantom{1}&1&0&1&0&\phantom{1}&\phantom{1}&\phantom{1} \\\hline \end{array} \end{aligned} \end{array}$ На втором шаге действует команда: $q_10\to q_20\Pi$ и на машине создается конфигурация: $\begin{array}{cc} \begin{matrix}{}\\(3)\end{matrix}&\qquad \begin{aligned}&\qquad\qquad\qquad\qquad\qquad q_2\\ &\begin{array}{c\|c\|c\|c\|c\|c\|c\|c\|c}\hline \phantom{1}&\phantom{1}&1&0&1&0&0&\phantom{1}&\phantom{1} \\\hline \end{array} \end{aligned} \end{array}$ Наконец, третий шаг обусловлен командой: $q_20\to q_01$ . В результате него создается конфигурация: $\begin{array}{cc} \begin{matrix}{}\\(4)\end{matrix}&\qquad \begin{aligned}&\qquad\qquad\qquad\qquad\qquad q_0\\ &\begin{array}{c\|c\|c\|c\|c\|c\|c\|c\|c}\hline \phantom{1}&\phantom{1}&1&0&1&0&1&\phantom{1}&\phantom{1} \\\hline \end{array} \end{aligned} \end{array}$ Эта конфигурация является заключительной, потому что машина оказалась в состоянии остановки $q_0$ . Таким образом, исходное слово 101 переработано машиной в слово 10101. Полученную последовательность конфигураций можно записать более коротким способом. Конфигурация (1) записывается в виде следующего слова в алфавите $A\cup Q\colon 10q_11$ (содержимое обозреваемой ячейки записано справа от состояния, в котором находится в данный момент машина). Далее, конфигурация (2) записывается так: $101q_10$ , конфигурация (3) — $1010q_20$ и, наконец, (4) — $1010q_01$ . Вся последовательность записывается так: $10q_11 \Rightarrow 101q_10 \Rightarrow 1010q_20 \Rightarrow 1010q_01.$ Приведем последовательность конфигураций при переработке этой машиной слова 11011, исходя из начального положения, при котором в состоянии $q_1$ обозревается крайняя левая ячейка, в которой содержится символ этого слова (самостоятельно проанализируйте каждый шаг работы машины, указывая, какая команда обусловила его): $\begin{aligned}&\begin{array}{cc} \begin{matrix}{}\\(1)\end{matrix}&\qquad \begin{aligned}&\qquad\quad\;~ q_1\\ &\begin{array}{c\|c\|c\|c\|c\|c\|c\|c\|c}\hline \phantom{1}&\phantom{1}&1&1&0&1&1&\phantom{1}&\phantom{1} \\\hline \end{array} \end{aligned} \end{array}\\ &\begin{array}{cc} \begin{matrix}{}\\(2)\end{matrix}&\qquad \begin{aligned}&\qquad\qquad\quad q_1\\ &\begin{array}{c\|c\|c\|c\|c\|c\|c\|c\|c}\hline \phantom{1}&\phantom{1}&1&1&0&1&1&\phantom{1}&\phantom{1} \\\hline \end{array} \end{aligned} \end{array}\\ &\begin{array}{cc} \begin{matrix}{}\\(3)\end{matrix}&\qquad \begin{aligned}&\qquad\qquad\qquad\,~~ q_1\\ &\begin{array}{c\|c\|c\|c\|c\|c\|c\|c\|c}\hline \phantom{1}&\phantom{1}&1&1&0&1&1&\phantom{1}&\phantom{1} \\\hline \end{array} \end{aligned} \end{array}\\ &\begin{array}{cc} \begin{matrix}{}\\(4)\end{matrix}&\qquad \begin{aligned}&\qquad\qquad\qquad\qquad\; q_2\\ &\begin{array}{c\|c\|c\|c\|c\|c\|c\|c\|c}\hline \phantom{1}&\phantom{1}&1&1&0&1&1&\phantom{1}&\phantom{1} \\\hline \end{array} \end{aligned} \end{array}\\ &\begin{array}{cc} \begin{matrix}{}\\(5)\end{matrix}&\qquad \begin{aligned}&\qquad\qquad\qquad\qquad\qquad q_2\\ &\begin{array}{c\|c\|c\|c\|c\|c\|c\|c\|c}\hline \phantom{1}&\phantom{1}&1&1&0&1&1&\phantom{1}&\phantom{1} \\\hline \end{array} \end{aligned} \end{array}\\ &\begin{array}{cc} \begin{matrix}{}\\(6)\end{matrix}&\qquad \begin{aligned}&\qquad\qquad\qquad\qquad\qquad\quad\;~ q_2\\ &\begin{array}{c\|c\|c\|c\|c\|c\|c\|c\|c}\hline \phantom{1}&\phantom{1}&1&1&0&1&1&0&\phantom{1} \\\hline \end{array} \end{aligned} \end{array}\\ &\begin{array}{cc} \begin{matrix}{}\\(7)\end{matrix}&\qquad \begin{aligned}&\qquad\qquad\qquad\qquad\qquad\quad\;~ q_2\\ &\begin{array}{c\|c\|c\|c\|c\|c\|c\|c\|c}\hline \phantom{1}&\phantom{1}&1&1&0&1&1&1&\phantom{1} \\\hline \end{array} \end{aligned} \end{array}\end{aligned}$ Более короткая запись этой последовательности конфигураций, те. процесса работы машины, будет $q_111011 \Rightarrow 1q_11011 \Rightarrow 11q_1011 \Rightarrow 110q_211 \Rightarrow 1101q_21 \Rightarrow 11011 q_20 \Rightarrow 11011q_01.$ Таким образом, слово 11011 переработано машиной в слово 110111. Пример 32.2. Машина Тьюринга задается внешним алфавитом $A= \{0,1,\ast\}$ (как и в предыдущем примере 0 — символ пустой ячейки), алфавитом внутренних состояний $Q=\{q_0,q_1,q_2,q_3\}$ и программой: $\begin{gathered}q_10\to q_10L,~ q_20\to q_31\Pi,~ q_30\to q_10L,~ q_11\to q_20L,~ q_21\to q_21L,\\ q_31\to q_31\Pi,~ q_1\ast\to q_00,~ q_2\ast\to q_2\ast L,~ q_3\ast\to q_3\ast\Pi. \end{gathered}$ Посмотрим, как эта машина перерабатывает некоторые слова, и постараемся обнаружить закономерность в ее работе. Предварительно заметим, что программа машины может быть записана также в виде следующей таблицы: $\begin{array}{\|c\|c\|c\|c\|}\hline A \setminus Q & q_1& q_2& q_3\\\hline 0& q_10L& q_11\Pi& q_10L\\ 1& q_20L& q_21L& q_31\Pi\\ \ast& q_00& q_2\ast L& q_3\ast\Pi\\\hline \end{array}$ Чтобы определить по таблице, что будет делать машина, находясь, например, в состоянии $q_2$ и наблюдая в обозреваемой ячейке символ 1, нужно найти в таблице клетку, находящуюся на пересечении столбца $q_2$ и строки, содержащей 1. В этой клетке записано $q_21L$ . Это означает, что на следующем шаге машина останется в прежнем состоянии $q_2$ , сохранит содержимое обозреваемой ячейки 1 и перейдет к обозрению следующей левой ячейки на ленте. Применим эту машину к слову $11\ast11$ . Вот последовательность конфигураций, возникающих в процессе работы машины (исходная конфигурация — стандартная начальная): $\begin{aligned} 111q_11 &\Rightarrow 11q_210 \Rightarrow 11q_210 \Rightarrow 1q_2110 \Rightarrow q_21110 \Rightarrow q_201110 \Rightarrow \\ & \Rightarrow q_31110 \Rightarrow 11q_3110 \Rightarrow 111q_310 \Rightarrow 111q_310 \Rightarrow 1111q_30 \Rightarrow \\ & \Rightarrow 111q_110 \Rightarrow 111q_200 \Rightarrow 11q_210 \Rightarrow 1q_2110 \Rightarrow q_21110 \Rightarrow \\ & \Rightarrow q_201110 \Rightarrow 1q_31110 \Rightarrow 11q_3110 \Rightarrow 111q_310 \Rightarrow 1111q_30 \Rightarrow \\ & \Rightarrow 1111q_30 \Rightarrow 1111q_10 \Rightarrow 1111q_000. \end{aligned}$ Предлагается проверить самостоятельно, что данная машина Тьюринга осуществляет следующие преобразования конфигураций: $\begin{gathered}11q_11 \Rightarrow 111q_00; \qquad 111q_11 \Rightarrow 11111q_00;\\ 1111q_11 \Rightarrow 11111q_00;\\ \qquad 111111q_11 \Rightarrow 1111111q_00.\end{gathered}$ Нетрудно заметить, что данная машина Тьюринга реализует операцию сложения: в результате ее работы на ленте записано подряд столько единиц, сколько их было всего записано по обе стороны от звездочки перед началом работы машины. Этот маленький опыт работы с машинами Тьюринга позволяет сделать некоторые выводы. Так тщательно описанное устройство этой машины (разбитая на ячейки лента, считывающая головка) по существу не имеет никакого значения. Машина Тьюринга — не что иное, как некоторое правило (алгоритм) для преобразования слов алфавита $A\cup Q$ , т. е. конфигураций. Таким образом, для определения машины Тьюринга нужно задать ее внешний и внутренний алфавиты, программу и указать, какие из символов обозначают пустую ячейку и заключительное состояние. Конструирование машин Тьюринга Создание (синтез) машин Тьюринга (т.е. написание соответствующих программ) является задачей значительно более сложной, нежели процесс применения данной машины к данным словам. Пример 32.3. Попытаемся построить такую машину Тьюринга, которая из $n$ записанных подряд единиц оставляла бы на ленте $n-2$ единицы, также записанные подряд, если $n \geqslant 2$ , и работала бы вечно, если $n=0$ или $n=1$ . В качестве внешнего алфавита возьмем двухэлементное множество $A=\{0;1\}$ . Количество необходимых внутренних состояний будет определено в процессе составления программы. Считаем, что машина начинает работать из стандартного начального положения, т.е. когда в состоянии $q_1$ обозревается крайняя правая единица из $n$ записанных на ленте. Начнем с того, что сотрем первую единицу, если она имеется, перейдем к обозрению следующей левой ячейки и сотрем там единицу, если она в этой ячейке записана. На каждом таком переходе машина должна переходить в новое внутреннее состояние, ибо в противном случае будут стерты вообще все единицы, записанные подряд. Вот команды, осуществляющие описанные действия: $q_11\to q_20L;\quad q_21\to q_30L.$ Машина находится в состоянии $q_3$ и обозревает третью справа ячейку из тех, в которых записано данное слово ( $n$ единиц). Не меняя содержимого обозреваемой ячейки, машина должна остановиться, т.е. перейти в заключительное состояние $q_0$ , независимо от содержимого ячейки. Вот эти команды: $q_30\to q_00;\quad q_31\to q_01.$ Теперь остается рассмотреть ситуации, когда на ленте записана всего одна единица или не записано ни одной. Если на ленте записана одна единица, то после первого шага (выполнив команду $q_11\to q_20L$ ) машина будет находиться в состоянии $q_2$ и будет обозревать вторую справа ячейку, в которой записан 0. По условию, в таком случае машина должна работать вечно. Это можно обеспечить, например, такой командой: $q_20\to q_20\Pi$ , выполняя которую шаг за шагом, машина будет двигаться по ленте неограниченно вправо (или протягивать ленту через считывающую головку справа налево). Наконец, если на ленте не записано ни одной единицы, то машина, по условию, также должна работать вечно. В этом случае в начальном состоянии $q_1$ обозревается ячейка с содержимым 0, и вечная работа машины обеспечивается следующей командой: $q_10\to q_10\Pi$ . Запишем составленную программу (функциональную схему) построенной машины Тьюринга в виде таблицы: $\begin{array}{\|c\|c\|c\|c\|} \hline A \setminus Q & q_1 & q_2 & q_3 \\ \hline 0 & q_10\Pi & q_20\Pi & q_00\\ \hline 1& q_00L & q_20L & q_01 \\ \hline \end{array}$ В заключение отметим следующее. Созданная нами машина Тьюринга может применяться не только к словам в алфавите $A=\{0;1\}$ , представляющим собой записанные подряд п единиц $(n \geqslant 2)$ . Она применима и ко многим другим словам в этом алфавите, например (проверьте самостоятельно) к словам: 1011, 10011, 111011, 11011, 1100111, 1001111, 10111, 10110111, 10010111 и т.д. (исходя из стандартного начального положения). С другой стороны, построенная машина не применима (т.е. при подаче этих слов на вход машины она работает вечно) не только к слову "1" или к слову, состоящему из одних нулей. Она не применима и к следующим словам (проверьте самостоятельно): 101, 1001, 11101, 101101, 1100101101 и т.д.. Вычислимые по Тьюрингу функции Определение 32.4. Функция называется вычислимой по Тьюрингу, если существует машина Тьюринга, вычисляющая ее, т.е. такая машина Тьюринга, которая вычисляет ее значения для тех наборов значений аргументов, для которых функция определена, и работающая вечно, если функция для данного набора значений аргументов не определена. Остается договориться о некоторых условностях для того, чтобы это определение стало до конца точным. Во-первых, напомним, что речь идет о функциях (или возможно о частичных функциях, т. е. не всюду определенных), заданных на множестве натуральных чисел и принимающих также натуральные значения. Во-вторых, нужно условиться, как записывать на ленте машины Тьюринга значения хи $x_1,x_2,\ldots,x_n$ аргументов функции $f(x_1,x_2,\ldots,x_n)$ , из какого положения начинать переработку исходного слова и, наконец, в каком положении получать значение функции. Это можно делать, например, следующим образом. Значения $x_1,x_2,\ldots,x_n$ аргументов будем располагать на ленте в виде следующего слова: $0\; \underbrace{1\,\ldots\,1}_{x_1}\; 0\; \underbrace{1\,\ldots\,1}_{x_2}\; 0\,\ldots\,0\; \underbrace{1\,\ldots\,1}_{x_n}\;0.$ Здесь полезно ввести следующие обозначения. Для натурального $x$ обозначаем: $1^x= \underbrace{1\,\ldots\,1}_{x},\quad 0^x= \underbrace{0\,\ldots\,0}_{x}.$ Дополнительно полагаем $0^0=1^0=\Lambda$ — пустое слово. Так что на слова $1^0=\Lambda,1^1=1,1^2=11,1^3=111,\ldots$ будем смотреть как на "изображения" натуральных чисел $0,1,2,3\ldots$ соответственно. Таким образом, предыдущее слово можно представить следующим образом: $01^{x_1}01^{x_2}0\ldots01^{x_n}0$ . Далее, начинать переработку данного слова будем из стандартного начального положения, т.е. из положения, при котором в состоянии $q_1$ обозревается крайняя правая единица записанного слова. Если функция $f(x_1,x_2,\ldots,x_n)$ определена на данном наборе значений аргументов, то в результате на ленте должно быть записано подряд $f(x_1,x_2,\ldots,x_n)$ единиц; в противном случае машина должна работать бесконечно. При выполнении всех перечисленных условий будем говорить, что машина Тьюринга вычисляет данную функцию. Таким образом, сформулированное определение 35.4 становится абсолютно строгим. Обратимся к примерам. Нетрудно понять, что машина Тьюринга из примера 32.2 по существу вычисляет функцию $f(x)=x+1$ , а машина Тьюринга из примера 32.3 вычисляет функцию $f(x)=x-2$ . Пример 32.5. Построим машину Тьюринга, вычисляющую функцию $f(x)=x\slash2$ . Эта функция не всюду определена: областью ее определения является лишь множество всех четных чисел. Поэтому, учитывая определение 32.4, нужно сконструировать такую машину Тьюринга, которая при подаче на ее вход четного числа давала бы на выходе половину этого числа, а при подаче нечетного — работала бы неограниченно долго. Сконструировать машину Тьюринга — значит написать (составить) ее программу. В этом процессе два этапа: сначала создается алгоритм вычисления значений функции, а затем он записывается на языке машины Тьюринга (программируется). В качестве внешнего алфавита возьмем двухэлементное множество $A\{0;1\}$ . В этом алфавите натуральное число х изображается словом $11\ldots1$ , состоящим из $x$ единиц, которое на ленте машины Тьюринга записывается в виде $x$ единиц, стоящих в ячейках подряд. Работа машины начинается из стандартного начального положения: $01\ldots1q_110$ (число единиц равно $x$ ). Сделаем начало вычислительного процесса таким: машина обозревает ячейки, двигаясь справа налево, и каждую вторую единицу превращает в 0. Такое начало обеспечивается следующими командами: $\begin{aligned}&(1)\colon\quad q_11\to q_21L;\\ &(2)\colon\quad q_21\to q_10L;\\ &(3)\colon\quad q_20\to q_20L. \end{aligned}$ Если число $x$ единиц нечетно, то машина продолжит движение по ленте влево неограниченно, т.е. будет работать бесконечно. Если же число $x$ единиц четно, то в результате выполнения команд создается конфигурация $q_10010101\ldots01010$ , в которой число единиц равно $x\slash2$ . Остается сдвинуть единицы так, чтобы между ними не стояли нули. Для осуществления этой процедуры предлагается следующий алгоритм. Будем двигаться по ленте вправо, ничего на ней не меняя, до первой единицы и перейдем за единицу. Передвижение осуществляется с помощью следующих команд: $\begin{aligned}&(4)\colon\quad q_10\to q_30\Pi;\\ &(5)\colon\quad q_30\to q_30\Pi;\\ &(6)\colon\quad q_31\to q_41\Pi. \end{aligned}$ В результате их выполнения получим конфигурацию $001q_4010101\ldots010100.$ () Заменим 0, перед которым остановились, на 1 и продвинемся вправо до ближайшего 0: $\begin{aligned}&(7)\colon\quad q_40\to q_51\Pi;\\ &(8)\colon\quad q_51\to q_51\Pi. \end{aligned}$ Получим конфигурацию $00111q_50101\ldots010100$ , в которой правее обозреваемой ячейки записаны "пары" $01,\ldots,01$ . Кроме того, на ленте одна единица записана лишняя. Продвинемся по ленте вправо до последней "пары" $01$ . Это можно сделать с помощью своеобразного цикла: $\begin{aligned}(9)\colon\quad &q_50\to q_60\Pi;\\ (10)\colon\quad &q_61\to q_51\Pi. \end{aligned}$ Получим конфигурацию $001110101\ldots01010q_600$ . Двигаться дальше вправо бессмысленно. Вернемся на две ячейки назад и заменим единицу из последней "пары" $01$ на ноль: $\begin{aligned}(11)\colon\quad &q_60\to q_70L;\\ (12)\colon\quad &q_70\to q_70L; \\ (13)\colon\quad &q_71\to q_80L. \end{aligned}$ Получим конфигурацию $001110101\ldots01q_800$ . Число единиц на ленте снова равно $x\slash2$ . Продвинемся влево на одну ячейку с помощью команды $(14)\colon\quad q_80\to q_90L.$ В результате чего получим конфигурацию $001110101\ldots010q_9100$ . Теперь уничтожим самую правую единицу и продвинемся по ленте влево до следующей единицы: $\begin{aligned}& (15)\colon\quad q_91\to q_{10}0L;\\ & (16)\colon\quad q_{10}0\to q_{10}0L. \end{aligned}$ Получим конфигурацию $001110101\ldots0q_{10}100,$ () в которой левее обозреваемой ячейки записана серия пар $10,10,\ldots,10$ (если читать справа налево). Теперь на ленте недостает одной единицы, т.е. число единиц равно $(x\slash2)-1$ . Продвинемся по ленте влево до последней "пары" $10$ . Это можно сделать с помощью цикла $\begin{aligned}& (17)\colon\quad q_{10}1\to q_{11}1L;\\ & (18)\colon\quad q_{11}0\to q_{10}0L, \end{aligned}$ выполнив который, придем к следующей конфигурации: $001q_{11}110101\ldots 0100$ . Вернемся вправо к ближайшему нулю и превратим его в единицу: $\begin{aligned}& (19)\colon\quad q_{11}1\to q_{12}1\Pi;\\ & (20)\colon\quad q_{12}1\to q_{12}1\Pi;& (21)\colon\quad q_{12}0\to q_{13}1\Pi. \end{aligned}$ Получим конфигурацию $001111q_{13}101\ldots0100$ , в которой число единиц снова равно $x\slash2$ . Если теперь перешагнем вправо по ленте через обозреваемую единицу и переведем машину в состояние $q_4$ с помощью команды $(22)\colon\quad q_{13}1\to q_{4}1\Pi,$ то придем к следующей конфигурации: $0011111q_401\ldots0100$ , которая по существу аналогична конфигурации (). В результате программа зацикливается (становится циклической): снова ближайший 0 превращается в 1, а самая правая 1 — в 0, затем машина возвращается к самому левому нулю, оказываясь в начале следующего цикла, и т.д. Как же завершается работа программы? В некоторый момент конфигурация будет иметь вид $00111\ldots1110q_{10}100$ . Выполнив команды (17), (18), придем к конфигурации $00111\ldots1q_{11}110100$ . Далее выполняются команды (19), (20), (21), что приводит к конфигурации: $00111\ldots111111q_{13}00$ . Остается остановить машину. Это делается с помощью команды $(23)\colon\quad q_{13}0\to q_{0}0L.$ Заключительная конфигурация имеет вид: $00111\ldots1111q_0100$ . Запишем программу машины Тьюринга в табличной форме: $\begin{array}{\|c\|c\|c\|}\hline Q \setminus A & 0 & 1\\ \hline q_{1} & q_{3}0\Pi & q_{2}1L\\ q_{2} & q_{2}0L & q_{1}0L\\ q_{3} & q_{3}0\Pi & q_{4}1\Pi\\ q_{4} & q_{5}1\Pi & \\ q_{5} & q_{6}0\Pi & q_{5}1\Pi\\ q_{6} & q_{7}0L & q_{5}1\Pi\\ q_{7} & q_{7}0L & q_{8}0L\\ q_{8} & q_{9}0L & q_{2}1L\\ q_{9} & & q_{10}0L\\ q_{10} & q_{10}0L & q_{11}1L\\ q_{11} & q_{10}0L & q_{12}1\Pi\\ q_{12} & q_{13}1\Pi & q_{13}1\Pi\\ q_{13} & q_{0}0L & q_{4}1\Pi\\ \hline \end{array}$ Предлагается самостоятельно проследить за работой этой машины Тьюринга, взяв в качестве исходных конкретные слова: 111, 1111, 111111, 1111111111. Правильная вычислимость функций на машине Тьюринга В предыдущем пункте мы рассмотрели вопрос о том, что значит и каким образом "данная машина Тьюринга вычисляет функцию $f(x_1,x_2,\ldots,x_n)$ ". Для этого нужно, чтобы каждое из чисел $x_1,x_2,\ldots,x_n$ было записано на ленту машины непрерывным массивом из соответствующего числа единиц, а сами массивы были разделены символом 0. Если функция $f(x_1,x_2,\ldots,x_n)$ определена на данном наборе значений аргументов, то в результате на ленте должно быть записано подряд $f(x_1,x_2,\ldots,x_n)$ единиц. При этом мы не очень строго относились к тому, в каком начальном положении машина начинает работать (часто это было стандартное начальное положение), в каком завершает работу и как эта работа протекает. В дальнейшем нам понадобится более сильное понятие вычислимости функции на машине Тьюринга — понятие правильной вычислимости. Определение 32.6. Будем говорить, что машина Тьюринга правильно вычисляет функцию $f(x_1,x_2,\ldots,x_n)$ , если начальное слово $q_101^{x_1}01^{x_2}0\ldots 01^{x_n}0$ она переводит в слово $q_001^{f(x_1,x_2,\ldots,x_n)}0\ldots0$ и при этом в процессе работы не пристраивает к начальному слову новых ячеек на ленте ни слева, ни справа. Если же функция $f$ не определена на данном наборе значений аргументов, то, начав работать из указанного положения, она никогда в процессе работы не будет надстраивать ленту слева. Пример 32.7. Приведем программы машин Тьюринга, правильно вычисляющих функции $S(x)=x+1$ и $O(x)=0$ . Функция $S(x)=x+1$ осуществляет перевод: $q_101^x0 \Rightarrow q_001^{x+1}$ . Ее программа: $q_10\to q_2\Pi,\quad q_21\to q_21\Pi,\quad q_20\to q_31,\quad q_31\to q_31L,\quad q_30\to q_00.$ Функция $O(x)=0$ осуществляет перевод: $q_101^x0 \Rightarrow q_000^{x+1}$ . Ее программа: $q_10\to q_20\Pi,\quad q_21\to q_21\Pi,\quad q_20\to q_30L,\quad q_31\to q_40,\quad q_40\to q_30L,\quad q_30\to q_00$ Соответствующую машину Тьюринга обозначили $\rm{O}$ . Пример 32.8. Построить две машины "левый сдвиг" $B^{-}$ и "правый сдвиг" $B^{+}$ . Первая из начального стандартного положения перерабатывает слово $01^x0$ в то же самое слово и останавливается, обозревая самую левую ячейку с нулем. Вторая машина из начального состояния, в котором обозревается левая ячейка с нулем, слово $01^x0$ перерабатывает в то же самое слово и останавливается, обозревая самую правую ячейку с нулем. Программа машины $B^{-}\colon\, q_10\to q_20L,q_21\to q_21L,q_20\to q_00$ . Ясно, что программа машины $B^{+}$ получается из программы предыдущей машины заменой символа "L" символом "П". Композиция машин Тьюринга Определение 32.9. Пусть заданы машины Тьюринга $\Theta_1$ и $\Theta_2$ , имеющие общий внешний алфавит $\{a_0,a_1,\ldots,a_m\}$ и алфавиты внутренних состояний $\{q_0,q_1,\ldots,q_n\}$ и $\{q_0,q'_1,\ldots,q'_n\}$ соответственно. Композицией (или произведением) машины $\Theta_1$ на машину $\Theta_2$ называется новая машина $\Theta$ с тем же внешним алфавитом $\{a_0,a_1,\ldots,a_m\}$ , внутренним алфавитом $\{q_0,q_1,\ldots,q_n,q_{n+1},\ldots,q_{n+t}\}$ и программой, получающейся следующим образом. Во всех командах из $\Theta_1$ содержащих символ остановки $q_0$ , заменяем последний на $q_{n+1}$ . Все остальные символы в командах из $\Theta_1$ остаются неизменными. В командах из $\Theta_2$ символ $q_0$ оставляем неизменным, а все остальные состояния $q'_i\,(i=1,\ldots,t)$ заменяем соответственно на $q_{n+i}$ . Совокупность всех так полученных команд образует программу машины-композиции $\Theta$ . Введенное понятие является удобным инструментом для конструирования машин Тьюринга. Покажем это на примере. Пример 32.10. Сконструируем машины Тьюринга, правильно вычисляющие функции-проекторы $I_m^n(x_1,x_2,\ldots,x_n)=x_m$ $(1 \leqslant m \leqslant n)$ . Рассмотрим сначала конкретный случай $n=2,n=3$ , т.е. функцию $I_2^3(x_1, x_2,x_3)=x_2$ . Мы должны переработать слово $q_101^{x_1}01^{x_2}01^{x_3}0$ в слово $q_001^{x_2}0$ . Будем применять к начальной конфигурации последовательно сконструированные ранее машины Тьюринга $B^{+},V,B^{-},\rm{O}\colon$ . $\begin{aligned}& & & q_101^{x_1}01^{x_2}01^{x_3}0;\\ &B^{+}\colon & & 01^{x_1}q01^{x_2}01^{x_3}0;\\ &V\colon & & 01^{x_2}q01^{x_1}01^{x_3}0;\\ &B^{+}\colon & & 01^{x_2}01^{x_1}q01^{x_3}0;\\ &\rm{O}\colon & & 01^{x_2}01^{x_1}q00^{x_3}0 ;\\ &B^{-}\colon & & 01^{x_2}q01^{x_1}00^{x_3}0;\\ &\rm{O}\colon & & 01^{x_2}q00^{x_1}00^{x_3}0;\\ &B^{-}\colon & & q01^{x_2}00^{x_1}00^{x_3}0.\end{aligned}$ Таким образом, функция $I_2^3(x_1,x_2,x_3)=x_2$ вычисляется следующей композицией машин: $B^{+}VB^{+}\rm{O}B^{-}\rm{O}B^{-}=B^{+}VB^{+}(\rm{O}B^{-})^2.$ Проверьте самостоятельно, что функция $I_2^2(x_1,x_2)=x_2$ вычисляется композицией $B^{+}V\rm{O}B^{-}$ . Теперь мы можем представить себе алгоритм построения композиции машин $B^{+},V, B^{-},\rm{O}$ для вычисления любой функции вида $I_m^n(x_1,x_2,\ldots,x_n)= x_m$ с помощью правого сдвига $B^{+}$ , применив его $m-1$ раз, нужно сначала достичь массива $01^{x_m}$ $(B^{+})^{m-1}\colon\quad 01^{x_1}0\ldots q01^{x_m}0\ldots01^{x_n}0.$ Затем, двигаясь влево, транспонировать (с помощью $V$ ) массив $01^{x_m}$ с каждым соседним слева массивом, пока массив $01^{x_m}$ не выйдет на первое место: $(V\cdot B^{-})^{m-1}\colon\quad q01^{x_m}01^{x_1}0\ldots 01^{x_{m-1}} 01^{x_{m+1}}0\ldots 01^{x_n}0.$ Теперь нужно дойти до крайнего правого массива с помощью (n-1)-кратного применения правого сдвига $B^{+}\colon$ $(B^{+})^{n-1}\colon\quad 01^{x_m}01^{x_1}0\ldots 01^{x_{m-1}}01^{x_{m+1}}0\ldots q01^{x_n}0.$ Наконец, нужно стирать последовательно справа налево все массивы единиц, кроме первого: $(\rm{O}B^{-})^{n-1}\colon\quad q01^{x_{m}}00^{x_{1}}0\ldots 00^{x_{m-1}} 00^{x_{m+1}}0\ldots 00^{x_{n}}0.$ Итак, данную функцию (правильно) вычисляет следующая машина Тьюринга: $(B^{+})^{m-1} (V\cdot B^{-})^{m-1} (B^{+})^{n-1} (\rm{O}\cdot B^{-})^{n-1}.$ При $n=3,m=2$ эта машина имеет вид: $B^{+}VB^{-}(B^{+})^2(\rm{O}B^{-})^2= B^{+}VB^{+}(\rm{O}B^{-})^2,$ т.е. совпадает с построенной выше машиной. При $n=2,m=2$ эта машина имеет вид: $B^{+}(VB^{-})B^{+}(\rm{O}B^{-})= B^{+}V\rm{O}B^{-}$ , т.е. также совпадает с соответствующей рассмотренной выше машиной Тьюринга. Тезис Тьюринга (основная гипотеза теории алгоритмов) Вернемся к интуитивному представлению об алгоритмах. Напомним, одно из свойств алгоритма заключается в том, что он представляет собой единый способ, позволяющий для каждой задачи из некоего бесконечного множества задач за конечное число шагов найти ее решение. На понятие алгоритма можно взглянуть и с несколько иной точки зрения. Каждую задачу из бесконечного множества задач можно выразить (закодировать) некоторым словом некоторого алфавита, а решение задачи — каким-то другим словом того же алфавита. В результате получим функцию, заданную на некотором подмножестве множества всех слов выбранного алфавита и принимающую значения в множестве всех слов того же алфавита. Решить какую-либо задачу — значит найти значение этой функции на слове, кодирующем данную задачу. А иметь алгоритм для решения всех задач данного класса — значит иметь единый способ, позволяющий в конечное число шагов "вычислять" значения построенной функции для любых значений аргумента из ее области определения. Таким образом, алгоритмическая проблема — по существу, проблема о вычислении значений функции, заданной в некотором алфавите. Остается уточнить, что значит уметь вычислять значения функции. Это значит вычислять значения функции с помощью подходящей машины Тьюринга. Для каких же функций возможно их тьюрингово вычисление? Многочисленные исследования ученых, обширный опыт показали, что такой класс функций чрезвычайно широк. Каждая функция, для вычисления значений которой существует какой-нибудь алгоритм, оказывалась вычислимой посредством некоторой машины Тьюринга. Это дало повод Тьюрингу высказать следующую гипотезу, называемую основной гипотезой теории алгоритмов, или тезисом Тьюринга: Для нахождения значений функции, заданной в некотором алфавите, тогда и только тогда существует какой-нибудь алгоритм, когда функция является вычислимой по Тьюрингу, т. е. когда она может вычисляться на подходящей машине Тьюринга. Это означает, что строго математическое понятие вычислимой (по Тьюрингу) функции является по существу идеальной моделью взятого из опыта понятия алгоритма. Данный тезис есть не что иное, как аксиома, постулат, выдвигаемый нами, о взаимосвязях нашего опыта с той математической теорией, которую мы под этот опыт хотим подвести. Конечно же данный тезис в принципе не может быть доказан методами математики, потому что он не имеет внутриматематического характера (одна сторона в тезисе — понятие алгоритма — не является точным математическим понятием). Он выдвинут исходя из опыта, и именно опыт подтверждает его состоятельность. Точно так же, например, не могут быть доказаны и математические законы механики; они открыты Ньютоном и многократно подтверждены опытом. Впрочем, не исключается принципиальная возможность того, что тезис Тьюринга будет опровергнут. Для этого должна быть указана функция, которая вычислима с помощью какого-нибудь алгоритма, но невычислима ни на какой машине Тьюринга. Но такая возможность представляется маловероятной (в этом одно из значений гипотезы): всякий алгоритм, который будет открыт, может быть реализован на машине Тьюринга. Дополнительные косвенные доводы в подтверждение этой гипотезы будут приведены в двух последующих параграфах, где рассматриваются другие формализации интуитивного понятия алгоритма и доказывается их равносильность с понятием машины Тьюринга. Машины Тьюринга и современные электронно-вычислительные машины Изучение машин Тьюринга и практика составления программ для них закладывают фундамент алгоритмического мышления, сущность которого состоит в том, что нужно уметь разделять тот или иной процесс вычисления или какой-либо другой деятельности на простые составляющие шаги. В машине Тьюринга расчленение (анализ) вычислительного процесса на простейшие операции доведено до предельной возможности: распознавание единичного рассмотренного вхождения символа, перемещение точки наблюдения данного ряда символов в соседнюю точку и изменение имеющейся в памяти информации. Конечно, такое мелкое дробление вычислительного процесса, реализуемого в машине Тьюринга, значительно его удлиняет. Но вместе с тем логическая структура процесса, расчлененного, образно выражаясь, до атомарного состояния, значительно упрощается и предстает в некотором стандартном виде, весьма удобном для теоретических исследований. (Именно такое расчленение на простейшие составляющие вычислительного процесса на машине Тьюринга дает еще один косвенный аргумент в пользу тезиса Тьюринга, обсуждавшегося в предыдущем пункте: всякая функция, вычисляемая с помощью какого-либо алгоритма, может быть вычислена на машине Тьюринга, потому что каждый шаг данного алгоритма можно расчленить на еще более мелкие операции, которые реализуются в машине Тьюринга.) Таким образом, понятие машины Тьюринга есть теоретический инструмент анализа алгоритмического процесса, а значит, анализа существа алгоритмического мышления. В современных ЭВМ алгоритмический процесс расчленен не на столь мелкие составляющие, как в машинах Тьюринга. Наоборот, создатели ЭВМ стремятся к известному укрупнению выполняемых машиной процедур (на этом пути, конечно, есть свои ограничения). Так, для выполнения операции сложения на машине Тьюринга составляется целая программа, а в современной ЭВМ такая операция является простейшей. Далее, машина Тьюринга обладает бесконечной внешней памятью (неограниченная в обе стороны лента, разбитая на ячейки). Но ни в одной реально существующей машине бесконечной памяти быть не может. Это говорит о том, что машины Тьюринга отображают потенциальную возможность неограниченного увеличения объема памяти современных ЭВМ. Наконец, можно провести более подробный сравнительный анализ работы современной ЭВМ и машины Тьюринга. В большинстве ЭВМ принята трехадресная система команд, обусловленная необходимостью выполнения бинарных операций, в которых участвует содержимое сразу трех ячеек памяти. Например, число из ячейки $a$ умножается на число из ячейки $b$ , и результат отправляется в ячейку $c$ . Существуют ЭВМ двухадресные и одноадресные. Так, одноадресная ЭВМ работает следующим образом: вызывается (в сумматор) число из ячейки $a$ ; в сумматоре происходит, например, умножение этого числа на число из ячейки $b$ ; результат отправляется из сумматора в ячейку $c$ . Машину Тьюринга можно считать одноадресной машиной, в которой система одноадресных команд упрощена еще больше: на каждом шаге работы машины команда предписывает замену лишь единственного знака, хранящегося в обозреваемой ячейке, а адрес обозреваемой ячейки при переходе к следующему такту может меняться лишь на единицу (обозрение соседней справа или слева ячейки ленты) или не меняться вовсе. Это удлиняет процесс, но в то же время резко унифицирует его, делает стандартным. Подводя итоги, можно сказать, что современные ЭВМ есть некие реальные физические модели машин Тьюринга, огрубленные с точки зрения теории, но созданные в целях реализации конкретных вычислительных процессов. В свою очередь, понятие машины Тьюринга и теория таких машин есть теоретический фундамент и обоснование современных ЭВМ. Математический форум (помощь с решением задач, обсуждение вопросов по математике). Если заметили ошибку, опечатку или есть предложения, напишите в комментариях.

Машины Тьюринга и тезис

Онлайн-сервисы

Нахождение НОД и НОК Разложение числа на простые множители Сравнения по модулю Операции над множествами Операции над векторами Разложение вектора по базису. Доказательство, что векторы образуют базис Чертёж треугольника по координатам вершин Решение треугольника Решение Пирамиды Построение Пирамиды по координатам вершин Чертёж многоугольника по координатам вершин Решение систем методом Крамера и Матричным Онлайн построение графика кривой 2-го порядка Определение вида кривой или поверхности 2-го порядка по инвариантам МНК и регрессионный анализ Онлайн + графики Онлайн число, сумма и дата прописью

Алгоритмы JavaScript

Алгоритмы поиска Алгоритмы сортировки Уникальные элементы массива Объединение, пересечение и разность массивов НОД и НОК Операции над матрицами Дата прописью

Введение в анализ

Функции: понятие, определение, графики Непрерывность функции Исследование функции и построение графика

Теория множеств

Множества: понятие, определение, примеры Точечные множества Замкнутые и открытые множества Мера множества Группы, кольца, поля в математике Поле комплексных чисел Кольцо многочленов Основная теорема алгебры и ее следствия

Математическая логика

Алгебра высказываний

Аксиоматика и логические рассуждения Методы доказательств теорем Алгебра высказываний и операции над ними Формулы алгебры высказываний Тавтологии алгебры высказываний Логическая равносильность формул Нормальные формы для формул высказываний Логическое следование формул Приложение алгебры высказываний для теорем Дедуктивные и индуктивные умозаключения Решение логических задач Принцип полной дизъюнкции

Булевы функции

Множества, отношения и функции в логике Булевы функции от одного и двух аргументов Булевы функции от n аргументов Системы булевых функций Применение булевых функций к релейно-контактным схемам Релейно-контактные схемы в ЭВМ Практическое применение булевых функций

Теория формального

Формализованное исчисление высказываний Полнота и другие свойства формализованного исчисления высказываний Независимость системы аксиом формализованного исчисления высказываний

Логика предикатов

Логика предикатов Логические операции над предикатами Кванторные операции над предикатами Формулы логики предикатов Тавтологии логики предикатов Преобразования формул и следование их предикатов Проблемы разрешения для общезначимости и выполнимости формул Применение логики предикатов в математике Строение математических теорем Аристотелева силлогистика и методы рассуждений Принцип полной дизъюнкции в предикатной форме Метод полной математической индукции Необходимые и достаточные условия Логика предикатов и алгебра множеств Формализованное исчисление предикатов

Неформальные и формаль-
ные аксиоматические теории

Неформальные аксиоматические теории Свойства аксиоматических теорий Формальные аксиоматические теории Формализация теории аристотелевых силлогизмов Свойства формализованного исчисления предикатов Формальные теории первого порядка Формализация математической теории

Теория алгоритмов

Интуитивное представление об алгоритмах Машины Тьюринга и тезис Рекурсивные функции Нормальные алгоритмы Маркова Разрешимость и перечислимость множеств Неразрешимые алгоритмические проблемы Теорема Гёделя о неполноте формальной арифметики

Математическая логика и компьютеры

Математическая логика и языки программирования Применение компьютеров для доказательства теорем математической логики Математическая логика и логическое программирование Математическая логика и информатика Математическая логика и искусственный интеллект

Дискретная математика

Множества и отношения

Теория множеств: понятия и определения Операции над множествами Кортеж и декартово произведение множеств Соответствия и бинарные отношения на множествах Операции над соответствиями на множествах Семейства множеств Специальные свойства бинарных отношений Отношения эквивалентности на множестве Упорядоченные множества Теорема о неподвижной точке Мощность множества Парадокс Рассела Метод характеристических функций

Группы и кольца

Алгебраические структуры и операции Группоиды, полугруппы, группы Кольца, тела, поля Области целостности в теории колец Модули и линейные пространства Подгруппы и подкольца Теорема Лагранжа о порядке конечной группы Гомоморфизмы групп и нормальные делители Гомоморфизмы и изоморфизмы колец Алгебра кватернионов

Полукольца и булевы алгебры

Полукольца: определение, аксиомы, примеры Замкнутые полукольца Полукольца и системы линейных уравнений Булевы алгебры и полукольца Решетки и полурешетки

Алгебраические системы

Алгебраические системы: модели и алгебры Подсистемы алгебраических систем Конгруэнции и фактор-системы Гомоморфизмы алгебраических систем Прямые произведения алгебраических систем Конечные булевы алгебры Многосортные алгебры

Теория графов

Теория графов: основные понятия и определения Способы представления графов Неориентированные и ориентированные деревья Остовное дерево и алгоритм Краскала Методы систематического обхода вершин графа Алгоритмы поиска в глубину и ширину в графах Задача о путях во взвешенных ориентированных графах Изоморфизм, гомоморфизм и автоморфизм графов Топологическая сортировка вершин графа Элементы цикломатики в теории графов

Булева алгебра и функции

Булевы функции и булев куб Таблицы булевых функций и булев оператор Равенство булевых функций. Фиктивные переменные Формулы и суперпозиции булевых функций Дизъюнктивные и конъюнктивные нормальные формы Построение минимальных ДНФ Теорема Поста и классы Критерий Поста Схемы из функциональных элементов

Конечные автоматы и регулярные языки

Конечные автоматы и регулярные языки Алфавит, слово, язык в программировании Порождающие грамматики (грамматики Хомского) Классификация грамматик и языков Регулярные языки и регулярные выражения Конечные автоматы Допустимость языка конечным автоматом Теорема Клини Детерминизация конечных автоматов Минимизация конечных автоматов Лемма о разрастании для регулярных языков Обоснование алгоритма детерминизации автоматов Конечные автоматы с выходом Морфизмы и конечные подстановки Машины Тьюринга

Контекстно-свободные языки

Контекстно-свободные языки и грамматики Приведенная форма КС-грамматики Лемма о разрастании для КС-языков Магазинные автоматы (автомат с магазинной памятью) Алгоритм построения МП-автомата по КС-грамматике Алгоритм построения КС-грамматики по МП-автомату Алгебраические свойства КС-языков Основное свойство суперпозиции КС-языков Пересечение контекстно-свободных языков Методы синтаксического анализа КС-языков Восходящий синтаксический анализ и LR(k)-грамматики Семантика формальных языков Принцип индукции по неподвижной точке Графовое представление МП-автоматов

Интегральное исчисление

Неопределённый и определённый

Неопределенный и определенный интегралы Свойства интегралов Интегрирование по частям Интегрирование методом замены переменной Интегрирование различных рациональных функций Интегрирование различных иррациональных функций Интегрирование различных тригонометрических функций Определенный интеграл и его основные свойства Необходимое и достаточное условие интегрируемости Теоремы существования первообразной Свойства определенных интегралов Несобственные интегралы Интегральное определение логарифмической функции

Приложения интегралов

Вычисление площадей плоских фигур Площади фигур в различных координатах Вычисление объемов тел с помощью интегралов Объём тела вращения Вычисление длин дуг кривых Формулы длины дуги регулярной кривой Кривизна плоской кривой Площадь поверхности вращения тела

Интегралы в физике

Статические моменты и координаты центра тяжести Теоремы Гульдина–Паппа Вычисление моментов инерции Другие приложения интегралов в физике

Основные интегралы

Интеграл Ньютона-Лейбница Интеграл Римана Интеграл Лебега

Вариационное исчисление

Примеры вариационных задач Дифференциальное уравнение Эйлера Функционалы, зависящие от нескольких функций Задача о минимуме кратного интеграла

Финансовый анализ

Анализ эффективности

Критерии и показатели эффективности предприятия Методы анализа эффективности деятельности Факторный анализ прибыли от операционной деятельности Анализ безубыточности предприятия Операционный рычаг и эффект финансового рычага Анализ и оценка состава, структуры и динамики доходов и расходов Анализ рентабельности и резервов устойчивого роста капитала Анализ распределения прибыли предприятия Анализ и оценка чувствительности показателей эффективности

Анализ устойчивости

Финансовая устойчивость и долгосрочная платежеспособность Характеристика типов финансовой устойчивости

Рыночная активность

Финансовый анализ рыночной активности Методика анализа рыночной активности Анализ и оценка дивидендного дохода на одну акцию

Инвестиционная деятельность

Инвестиции: экономическая сущность и классификация Государственное регулирование инвестиционной деятельности Источники финансовых ресурсов на капитальные вложения Инвестиции в основные фонды Оценка состояния основных фондов Амортизация основных фондов Капитальное строительство в инвестиционном процессе Планирование инвестиций в форме капитальных вложений Экономическая эффективность инвестиций Финансирование капитальных вложений Кредитование капитальных вложений Кредитоспособность Финансирование и кредитование затрат Финансирование и кредитование инвестиционной деятельности потребительской кооперации Финансирование и кредитование капитальных вложений потребительской кооперации Инвестиционное строительное проектирование

Анализ инвестиций

Инвестиции и инвестиционная деятельность предприятия Задачи финансового анализа инвестиций предприятия Учет фактора времени в инвестиционной деятельности Аннуитет и финансовая рента в инвестициях Учет фактора инфляции при инвестировании Оценка фактора риска инвестиционного проекта Методы оценки эффективности инвестиций Показатели эффективности инвестиционного проекта

Стоимость компании

Концепция построения международных стандартов финансовой отчетности (МСФО) Экономическое содержание международных стандартов финансовой отчётности Цели и принципы оценки стоимости акций и активов компании Оценка акций и активов предприятия по справедливой стоимости Методы оценки справедливой стоимости акций предприятия Затратный подход к оценки стоимости компаний и акций Сравнительный подход к оценки стоимости предприятий и акций Доходный подход к оценке стоимости компании и акций Выбор ставки дисконтирования при инвестировании в акции Метод капитализации прибыли Сравнение подходов к оценке стоимости компаний и пакетов акций

Форвардные контракты

Форвардный контракт и цена Форвардная цена акции на бирже Цена форвардного контракта инвестора Форвардная цена акции с учетом величины дивиденда Форвардная цена акции с учетом ставки дивиденда Форвардная цена валюты на рынке форекс Форвардный валютный курс и инфляция на рынке Форвардная цена товара и спотовый рынок Форвардная цена при различии ставок по кредитам и депозитам Синтетический форвардный контракт на акции и валюту

Теория вероятностей

Основные понятия теории вероятностей Зависимые и независимые случайные события Повторные независимые испытания Формула Бернулли Одномерные случайные величины Многомерные случайные величины Функции случайных величин Законы распределения целочисленных случайных величин Законы распределения непрерывных случайных величин Предельные теоремы теории вероятностей Закон больших чисел и предельные теоремы Вероятностные закономерности

Математическая статистика

Элементы математической статистики Выборочный метод Оценки параметров генеральной совокупности Статистические гипотезы Критерии согласия Теоретические и эмпирические частоты

Теория очередей (СМО)

Определение системы массового обслуживания Уравнения Колмогорова Предельные вероятности состояний Определение СМО с отказами Определение СМО с ожиданием (очередью)

Аналитическая геометрия

Векторная алгебра

Метрические понятия и аксиомы геометрии Равенство и подобие геометрических фигур Бинарные отношения Вектор, его направление и длина Линейные операции над векторами Линейная зависимость и независимость векторов Отношение коллинеарных векторов Проекции векторов на прямую и на плоскость Угол между векторами Ортогональные проекции векторов Координата вектора на прямой и базис Координаты вектора на плоскости и базис Координаты вектора в пространстве и базис Операции над векторами в координатной форме Ортогональный и ортонормированный базисы Cкалярное произведение векторов и его свойства Выражение скалярного произведения через координаты векторов Векторное произведение векторов и его свойства Смешанное произведение векторов и его свойства Ориентированные площади и объемы Двойное векторное произведение и его свойства Применение векторов в задачах на аффинные свойства фигур Применение произведений векторов при решении геометрических задач Применение векторной алгебры в механике

Системы координат

Прямоугольные координаты Преобразования прямоугольных координат Полярная система координат Цилиндрическая система координат Сферические координаты Аффинные координаты Аффинные преобразования координат Аффинные преобразования плоскости Примеры аффинных преобразований плоскости Аффинные преобразования пространства Многомерное координатное пространство Линейные и аффинные подпространства Скалярное произведение n-мерных векторов Преобразования систем координат

Геометрия на плоскости

Алгебраические линии на плоскости Общие уравнения геометрических мест точек Алгебраические уравнения линий на плоскости Уравнения прямой, проходящей через точку перпендикулярно вектору Уравнения прямой, проходящей через точку коллинеарно вектору Уравнения прямой, проходящей через две точки Уравнения прямой с угловым коэффициентом Взаимное расположение прямых Примеры задач с прямыми на плоскости Системы неравенств с двумя неизвестными Системы линейных уравнений с двумя неизвестными

Линии 2-го порядка

Канонические уравнения линий второго порядка Порядок приведения уравнения линии к каноническому виду Эллипс Гипербола Парабола Квадратичные неравенства с двумя неизвестными Применение линий 1-го и 2-го порядков в задачах на экстремум функций

Инварианты линий

Классификация линий 2-го порядка по инвариантам Приведение уравнения линии к каноническому виду по инвариантам

Геометрия в пространстве

Способы задания ГМТ в пространстве Алгебраические уравнения поверхностей Уравнения плоскости, проходящей через точку перпендикулярно вектору Уравнения плоскости, компланарной двум неколлинеарным векторам Уравнения плоскости, проходящей через три точки Взаимное расположение плоскостей Типовые задачи с плоскостями Уравнения прямых в пространстве Взаимное расположение прямых в пространстве Типовые задачи с прямыми в пространстве

Поверхности 2-го порядка

Канонические уравнения поверхностей Порядок приведения уравнения поверхности к каноническому виду Поверхности второго порядка Эллипсоиды Гиперболоиды Конусы Параболоиды Применение поверхностей 1-го и 2-го порядков в задачах на экстремум функций

Инварианты поверхностей

Классификация поверхностей 2-го порядка по инвариантам Квадратичные неравенства с тремя неизвестными Приведение уравнения поверхности к канониче-скому виду по инвариантам

Линейная алгебра

Матрицы и операции

Линейные операции над матрицами Умножение матриц Возведение матриц в степень Многочлены от матриц Транспонирование и сопряжение матриц Блочные матрицы Произведение и сумма матриц Кронекера Метод Гаусса приведения матрицы к ступенчатому виду Элементарные преобразования матриц

Определители

Определители матриц и их основные свойства Формула полного разложения определителя Формула Лапласа полного разложения определителя Определитель произведения матриц Методы вычисления определителей

Ранг матрицы

Линейная зависимость и линейная независимость строк (столбцов) матрицы Ранг матрицы и базисный минор матрицы Методы вычисления ранга матрицы Ранг системы столбцов (строк)

Обратная матрица

Обратные матрицы и их свойства Ортогональные и унитарные матрицы Способы нахождения обратной матрицы Матричные уравнения Односторонние обратные матрицы Скелетное разложение матрицы Полуобратная матрица Псевдообратная матрица

Системы уравнений

Системы линейных алгебраических уравнений Метод Гаусса решения систем линейных уравнений Структура общего решения системы уравнений Решение систем с помощью полуобратных матриц Псевдорешения системы линейных уравнений

Функциональные матрицы

Функциональные матрицы скалярного аргумента Производные матриц по векторному аргументу Линейные и квадратичные формы и их преобразования Приведение форм к каноническому виду Закон инерции вещественных квадратичных форм Знакоопределенность форм вещественных квадратичных Формы и исследование функций на экстремум

Многочленные матрицы

Многочленные матрицы (лямбда-матрицы) Операции над лямбда-матрицами Простые преобразования многочленных матриц Инвариантные множители многочленной матрицы

Функции от матриц

Собственные векторы и значения матрицы Подобие числовых матриц Характеристический многочлен матрицы Минимальный многочлен матрицы Теорема Гамильтона-Кэли Жорданова форма матрицы Приведение матрицы к жордановой форме Многочлены от матриц Применение многочленов от матриц Функции от матриц

Линейные пространства

Линейные пространства: определение и примеры Линейная зависимость и независимость n-мерных векторов Размерность и базис линейного пространства Преобразования координат в линейном пространстве Изоморфизм линейных пространств

Подпространства

Подпространства линейного пространства Пересечение и сумма подпространств Способы описания подпространств Нахождение дополнения и суммы подпространств Нахождение пересечения подпространств

Линейные отображения

Линейные многообразия Линейные отображения Матрица линейного отображения Ядро и образ линейного отображения

Линейные операторы

Линейные операторы (преобразования) Инвариантные подпространства Собственные векторы и значения оператора Свойства собственных векторов операторов Канонический вид линейного оператора Методика приведения линейного преобразования к каноническому виду

Евклидовы пространства

Комплексный анализ

Комплексные числа

Комплексные числа в алгебраической форме Комплексные числа в тригонометрической и показательной формах Множества на комплексной плоскости Последовательности и ряды комплексных чисел

Комплексные функции

Функции комплексного переменного. Предел, непрерывность и производная Элементарные функции комплексного переменного Дифференцирование функций комплексного переменного Аналитические функции и их свойства Конформные отображения
и их свойства Интегрирование функций комплексного переменного

Функциональные ряды в комплексной области

Функциональные ряды и последовательности Степенные ряды и их свойства Разложение функций в степенные ряды Нули аналитических функций Ряд Лорана и разложение функций по целым степеням

Особые точки, Вычеты

Изолированные особые точки функций и полюсы Вычеты и их применение Вычисление интегралов с помощью вычетов Вычеты и расположение нулей многочлена

Операционное исчисление

Преобразование Лапласа и его свойства Решение ДУ операционным методом Анализ выходных процессов линейных стационарных систем Z-преобразование и его свойства

Дифференциальные уравнения

ДУ первого порядка

Основные понятия и определения ДУ Метод изоклин для ДУ 1-го порядка Метод последовательных приближений ДУ с разделяющимися переменными Однородные ДУ Линейные ДУ 1-го порядка Дифференциальное уравнение Бернулли ДУ в полных дифференциалах Интегрирующий множитель ДУ, не разрешенные относительно производной Дифференциальное уравнение Риккати Составление ДУ семейств линий Задачи на траектории Особые решения ДУ

ДУ высших порядков

Понятия и определения ДУ высших порядков ДУ, допускающие понижение порядка Линейная независимость функций Определители Вронского и Грама Однородные и неоднородные дифференциальные уравнения Задача Коши и Уравнение Эйлера Линейные ДУ с переменными коэффициентами Метод Лагранжа решения ДУ Краевые задачи для ДУ высших порядков Разложение решения ДУ в степенной ряд Разложение решения ДУ в обобщенный степенной ряд Нахождение периодических решений ДУ Асимптотическое интегрирование ДУ

Системы ДУ

Системы ДУ: понятия и определения Сведение системы ДУ к одному уравнению Нахождение интегрируемых комбинаций Интегрирование однородных линейных систем ДУ Методы интегрирования неоднородных систем ДУ Преобразование Лапласа и решение ДУ и систем

Теория устойчивости

Устойчивость решений ДУ по Ляпунову Простейшие типы точек покоя Метод функций Ляпунова Устойчивость решений ДУ по первому приближению Критерии устойчивости Рауса–Гурвица и Михайлова ДУ с малым параметром при производной

Численные методы

Методы алгебры

Численные методы линейной алгебры Численные методы решения СЛАУ Итерационный метод Шульца обратной матрицы Методы решения задач о собственных значениях и векторах матрицы Методы решения нелинейных уравнений Методы решения систем нелинейных уравнений

Методы теории приближений

Методы приближения сеточных функций Методы функциональной интерполяции Методы интегрально-дифференциальной интерполяции Методы интегрального сглаживания Методы интерполяции и сглаживания сплайнами Методы численного дифференцирования и интегрирования Методы численного дифференцирования Методы численного интегрирования

Методы решения обыкновенных ДУ

Численные методы решения задачи Коши Разностные схемы для решения задачи Коши Составные схемы для решения задачи Коши Экстраполяционные методы решения задачи Коши Непрерывно-дискретные методы решения задачи Коши Численные методы решения краевых задач

Методы решения ДУ в частных производных

Численные методы решения уравнений математической физики с двумя переменными Принципы построения разностных схем для уравнений в частных производных Разностные схемы решения уравнений в частных производных 1-го порядка Разностные схемы решения уравнений в частных производных 2-го порядка Численные методы решения уравнений в частных производных Численные методы решения уравнений математической физики с тремя переменными

Машины Тьюринга и тезис

Введение понятия машины Тьюринга явилось одной из первых и весьма удачных попыток дать точный математический эквивалент для общего интуитивного представления об алгоритме. Это понятие названо по имени английского математика, сформулировавшего его в 1937 г., за 9 лет до появления первой электронно-вычислительной машины.

Определение машины Тьюринга

Машина Тьюринга есть математическая (воображаемая) машина, а не машина физическая. Она есть такой же математический объект, как функция, производная, интеграл, группа и т.д. И так же как и другие математические понятия, понятие машины Тьюринга отражает объективную реальность, моделирует некие реальные процессы. Именно Тьюринг предпринял попытку смоделировать действия математика (или другого человека), осуществляющего некую умственную созидательную деятельность. Такой человек, находясь в определенном "умонастроении" ("состоянии"), просматривает некоторый текст. Затем он вносит в этот текст какие-то изменения, проникается новым "умонастроением" и переходит к просмотру последующих записей.

Машина Тьюринга действует примерно также. Ее удобно представлять в виде автоматически работающего устройства. В каждый дискретный момент времени устройство, находясь в некотором состоянии, обозревает содержимое одной ячейки протягиваемой через устройство ленты и делает шаг, заключающийся в том, что устройство переходит в новое состояние, изменяет (или оставляет без изменения) содержимое обозреваемой ячейки и переходит к обозрению следующей ячейки — справа или слева. Причем шаг осуществляется на основании предписанной команды. Совокупность всех команд представляет собой программу машины Тьюринга.

Опишем теперь машину Тьюринга $\Theta$ более тщательно. Машина $\Theta$ располагает конечным числом знаков (символов, букв), образующих так называемый внешний алфавит $A=\{a_0,a_1,\ldots,a_n\}$ . В каждую ячейку обозреваемой ленты в каждый дискретный момент времени может быть записан только один символ из алфавита $A$ . Ради единообразия удобно считать, что среди букв внешнего алфавита $A$ имеется "пустая буква", и именно она записана в пустую ячейку ленты. Условимся, что "пустой буквой" или символом пустой ячейки является буква $a_0$ . Лента предполагается неограниченной в обе стороны, но в каждый момент времени на ней записано конечное число непустых букв.

Далее, в каждый момент времени машина $\Theta$ способна находиться в одном состоянии из конечного числа внутренних состояний, совокупность которых $Q=\{q_0,q_1,\ldots,q_m\}$ . Среди состояний выделяются два — начальное $q_1$ и заключительное (или состояние остановки) $q_0$ . Находясь в состоянии $q_1$ машина начинает работать. Попав в состояние $q_0$ , машина останавливается.

Работа машины $\Theta$ определяется программой (функциональной схемой). Программа состоит из команд. Каждая команда $T(i,j)$ $(i=1,2,\ldots,m;\, j=0,1,\ldots,n)$ представляет собой выражение одного из следующих видов:

$q_ia_j\to q_ka_lC;\quad q_ia_j\to q_ka_l\Pi;\quad q_ia_j\to q_ka_lL,$

(32.1)

где $0 \leqslant k \leqslant m,~ 0 \leqslant l \leqslant n$ . В выражениях первого вида символ $C$ будем часто опускать.

Как же работает машина Тьюринга? Находясь в какой-либо момент времени в незаключительном состоянии (т. е. в состоянии, отличном от $q_0$ ), машина совершает шаг, который полностью определяется ее текущим состоянием $q_i$ и символом $a_j$ , воспринимаемым ею в данный момент на ленте. При этом содержание шага регламентировано соответствующей командой $T(i,j)\colon q_ia_j\to q_ka_iX$ , где $X\in\{C,\Pi,L\}$ . Шаг заключается в том, что:

1) содержимое $a_j$ обозреваемой на ленте ячейки стирается и на его место записывается символ $a_i$ (который может совпадать с $a_j$ );

2) машина переходит в новое состояние $q_k$ (оно также может совпадать с предыдущим состоянием $q_i$ );

3) машина переходит к обозрению следующей правой ячейки от той, которая обозревалась только что, если $X=\Pi$ , или к обозрению следующей левой ячейки, если $X=L$ , или же продолжает обозревать ту же ячейку ленты, если $X=C$ .

В следующий момент времени (если $q_k\ne q_0$ ) машина делает шаг, регламентированный командой $T(k,l)\colon q_ka_i\to q_ra_sX$ и т.д.

Поскольку работа машины, по условию, полностью определяется ее состоянием $q_i$ в данный момент и содержимым $a_j$ обозреваемой в этот момент ячейки, то для каждых $q_i$ и $a_j~(i=1,2,\ldots,m;\, j=0,1,\ldots,n)$ программа машины должна содержать одну и только одну команду, начинающуюся символами $q_ia_j$ . Поэтому программа машины Тьюринга с внешним алфавитом $A=\{a_0,a_1,\ldots,a_n\}$ и алфавитом внутренних состояний $Q=\{q_0,q_1,\ldots,q_m\}$ содержит $m(n+1)$ команд.

Словом в алфавите $A$ или в алфавите $Q$ , или в алфавите $A\cup Q$ называется любая последовательность букв соответствующего алфавита. Под k-й конфигурацией будем понимать изображение ленты машины с информацией, сложившейся на ней к началу k-то шага (или слово в алфавите $A$ , записанное на ленту к началу k-ro шага), с указанием того, какая ячейка обозревается в этот шаг и в каком состоянии находится машина. Имеют смысл лишь конечные конфигурации, т.е. такие, в которых все ячейки ленты, за исключением, быть может, конечного числа, пусты. Конфигурация называется заключительной, если состояние, в котором при этом находится машина, заключительное.

Если выбрать какую-либо незаключительную конфигурацию машины Тьюринга в качестве исходной, то работа машины будет состоять в том, чтобы последовательно (шаг за шагом) преобразовывать исходную конфигурацию в соответствии с программой машины до тех пор, пока не будет достигнута заключительная конфигурация. После этого работа машины Тьюринга считается закончившейся, а результатом работы считается достигнутая заключительная конфигурация.

Будем говорить, что непустое слово а в алфавите $A\setminus\{a_0\}= \{a_1,\ldots,a_n\}$ воспринимается машиной в стандартном положении, если оно записано в последовательных ячейках ленты, все другие ячейки пусты, и машина обозревает крайнюю справа ячейку из тех, в которых записано слово $\alpha$ . Стандартное положение называется начальным (заключительным), если машина, воспринимающая слово в стандартном положении, находится в начальном состоянии $q_1$ (соответственно в состоянии остановки $q_0$ ). Наконец, будем говорить, что слово $\alpha$ перерабатывается машиной в слово $\beta$ , если от слова $\alpha$ , воспринимаемого в начальном стандартном положении, машина после выполнения конечного числа команд приходит к слову $\beta$ , воспринимаемому в положении остановки.

Применение машин Тьюринга к словам

Проиллюстрируем на примерах все введенные понятия, связанные с машинами Тьюринга.

Пример 32.1. Дана машина Тьюринга с внешним алфавитом $A=\{0;1\}$ (здесь 0 — символ пустой ячейки), алфавитом внутренних состояний $Q=\{q_0,q_1,q_2\}$ и со следующей функциональной схемой (программой):

$q_10\to q_2o\Pi;\quad q_20\to q_01;\quad q_11\to q_11\Pi;\quad q_21\to q_21\Pi.$

Посмотрим, в какое слово переработает эта машина слово 101, исходя из стандартного начального положения. Будем последовательно выписывать конфигурации машины при переработке ею этого слова. Имеем стандартное начальное положение:

$\begin{array}{cc} \begin{matrix}{}\\(1)\end{matrix}&\qquad \begin{aligned}&\qquad\qquad\qquad\,~~ q_1\\ &\begin{array}{c|c|c|c|c|c|c|c|c}\hline \phantom{1}&\phantom{1}&1&0&1&\phantom{1}&\phantom{1}&\phantom{1}&\phantom{1} \\\hline \end{array} \end{aligned} \end{array}$

На первом шаге действует команда: $q_11\to q_11\Pi$ . В результате на машине создается следующая конфигурация:

$\begin{array}{cc} \begin{matrix}{}\\(2)\end{matrix}&\qquad \begin{aligned}&\qquad\qquad\qquad\qquad~ q_1\\ &\begin{array}{c|c|c|c|c|c|c|c|c}\hline \phantom{1}&\phantom{1}&1&0&1&0&\phantom{1}&\phantom{1}&\phantom{1} \\\hline \end{array} \end{aligned} \end{array}$

На втором шаге действует команда: $q_10\to q_20\Pi$ и на машине создается конфигурация:

$\begin{array}{cc} \begin{matrix}{}\\(3)\end{matrix}&\qquad \begin{aligned}&\qquad\qquad\qquad\qquad\qquad q_2\\ &\begin{array}{c|c|c|c|c|c|c|c|c}\hline \phantom{1}&\phantom{1}&1&0&1&0&0&\phantom{1}&\phantom{1} \\\hline \end{array} \end{aligned} \end{array}$

Наконец, третий шаг обусловлен командой: $q_20\to q_01$ . В результате него создается конфигурация:

$\begin{array}{cc} \begin{matrix}{}\\(4)\end{matrix}&\qquad \begin{aligned}&\qquad\qquad\qquad\qquad\qquad q_0\\ &\begin{array}{c|c|c|c|c|c|c|c|c}\hline \phantom{1}&\phantom{1}&1&0&1&0&1&\phantom{1}&\phantom{1} \\\hline \end{array} \end{aligned} \end{array}$

Эта конфигурация является заключительной, потому что машина оказалась в состоянии остановки $q_0$ .

Таким образом, исходное слово 101 переработано машиной в слово 10101.

Полученную последовательность конфигураций можно записать более коротким способом. Конфигурация (1) записывается в виде следующего слова в алфавите $A\cup Q\colon 10q_11$ (содержимое обозреваемой ячейки записано справа от состояния, в котором находится в данный момент машина). Далее, конфигурация (2) записывается так: $101q_10$ , конфигурация (3) — $1010q_20$ и, наконец, (4) — $1010q_01$ . Вся последовательность записывается так:

$10q_11 \Rightarrow 101q_10 \Rightarrow 1010q_20 \Rightarrow 1010q_01.$

Приведем последовательность конфигураций при переработке этой машиной слова 11011, исходя из начального положения, при котором в состоянии $q_1$ обозревается крайняя левая ячейка, в которой содержится символ этого слова (самостоятельно проанализируйте каждый шаг работы машины, указывая, какая команда обусловила его):

$\begin{aligned}&\begin{array}{cc} \begin{matrix}{}\\(1)\end{matrix}&\qquad \begin{aligned}&\qquad\quad\;~ q_1\\ &\begin{array}{c|c|c|c|c|c|c|c|c}\hline \phantom{1}&\phantom{1}&1&1&0&1&1&\phantom{1}&\phantom{1} \\\hline \end{array} \end{aligned} \end{array}\\ &\begin{array}{cc} \begin{matrix}{}\\(2)\end{matrix}&\qquad \begin{aligned}&\qquad\qquad\quad q_1\\ &\begin{array}{c|c|c|c|c|c|c|c|c}\hline \phantom{1}&\phantom{1}&1&1&0&1&1&\phantom{1}&\phantom{1} \\\hline \end{array} \end{aligned} \end{array}\\ &\begin{array}{cc} \begin{matrix}{}\\(3)\end{matrix}&\qquad \begin{aligned}&\qquad\qquad\qquad\,~~ q_1\\ &\begin{array}{c|c|c|c|c|c|c|c|c}\hline \phantom{1}&\phantom{1}&1&1&0&1&1&\phantom{1}&\phantom{1} \\\hline \end{array} \end{aligned} \end{array}\\ &\begin{array}{cc} \begin{matrix}{}\\(4)\end{matrix}&\qquad \begin{aligned}&\qquad\qquad\qquad\qquad\; q_2\\ &\begin{array}{c|c|c|c|c|c|c|c|c}\hline \phantom{1}&\phantom{1}&1&1&0&1&1&\phantom{1}&\phantom{1} \\\hline \end{array} \end{aligned} \end{array}\\ &\begin{array}{cc} \begin{matrix}{}\\(5)\end{matrix}&\qquad \begin{aligned}&\qquad\qquad\qquad\qquad\qquad q_2\\ &\begin{array}{c|c|c|c|c|c|c|c|c}\hline \phantom{1}&\phantom{1}&1&1&0&1&1&\phantom{1}&\phantom{1} \\\hline \end{array} \end{aligned} \end{array}\\ &\begin{array}{cc} \begin{matrix}{}\\(6)\end{matrix}&\qquad \begin{aligned}&\qquad\qquad\qquad\qquad\qquad\quad\;~ q_2\\ &\begin{array}{c|c|c|c|c|c|c|c|c}\hline \phantom{1}&\phantom{1}&1&1&0&1&1&0&\phantom{1} \\\hline \end{array} \end{aligned} \end{array}\\ &\begin{array}{cc} \begin{matrix}{}\\(7)\end{matrix}&\qquad \begin{aligned}&\qquad\qquad\qquad\qquad\qquad\quad\;~ q_2\\ &\begin{array}{c|c|c|c|c|c|c|c|c}\hline \phantom{1}&\phantom{1}&1&1&0&1&1&1&\phantom{1} \\\hline \end{array} \end{aligned} \end{array}\end{aligned}$

Более короткая запись этой последовательности конфигураций, те. процесса работы машины, будет

$q_111011 \Rightarrow 1q_11011 \Rightarrow 11q_1011 \Rightarrow 110q_211 \Rightarrow 1101q_21 \Rightarrow 11011 q_20 \Rightarrow 11011q_01.$

Таким образом, слово 11011 переработано машиной в слово 110111.

Пример 32.2. Машина Тьюринга задается внешним алфавитом $A= \{0,1,\ast\}$ (как и в предыдущем примере 0 — символ пустой ячейки), алфавитом внутренних состояний $Q=\{q_0,q_1,q_2,q_3\}$ и программой:

$\begin{gathered}q_10\to q_10L,~ q_20\to q_31\Pi,~ q_30\to q_10L,~ q_11\to q_20L,~ q_21\to q_21L,\\ q_31\to q_31\Pi,~ q_1\ast\to q_00,~ q_2\ast\to q_2\ast L,~ q_3\ast\to q_3\ast\Pi. \end{gathered}$

Посмотрим, как эта машина перерабатывает некоторые слова, и постараемся обнаружить закономерность в ее работе. Предварительно заметим, что программа машины может быть записана также в виде следующей таблицы:

$\begin{array}{|c|c|c|c|}\hline A \setminus Q & q_1& q_2& q_3\\\hline 0& q_10L& q_11\Pi& q_10L\\ 1& q_20L& q_21L& q_31\Pi\\ \ast& q_00& q_2\ast L& q_3\ast\Pi\\\hline \end{array}$

Чтобы определить по таблице, что будет делать машина, находясь, например, в состоянии $q_2$ и наблюдая в обозреваемой ячейке символ 1, нужно найти в таблице клетку, находящуюся на пересечении столбца $q_2$ и строки, содержащей 1. В этой клетке записано $q_21L$ . Это означает, что на следующем шаге машина останется в прежнем состоянии $q_2$ , сохранит содержимое обозреваемой ячейки 1 и перейдет к обозрению следующей левой ячейки на ленте.

Применим эту машину к слову $11\ast11$ . Вот последовательность конфигураций, возникающих в процессе работы машины (исходная конфигурация — стандартная начальная):

$\begin{aligned} 11*1q_11 &\Rightarrow 11*q_210 \Rightarrow 11q_2*10 \Rightarrow 1q_21*10 \Rightarrow q_211*10 \Rightarrow q_2011*10 \Rightarrow \\ & \Rightarrow q_311*10 \Rightarrow 11q_31*10 \Rightarrow 111q_3*10 \Rightarrow 111*q_310 \Rightarrow 111*1q_30 \Rightarrow \\ & \Rightarrow 111*q_110 \Rightarrow 111q_2*00 \Rightarrow 11q_21*0 \Rightarrow 1q_211*0 \Rightarrow q_2111*0 \Rightarrow \\ & \Rightarrow q_20111*0 \Rightarrow 1q_3111*0 \Rightarrow 11q_311*0 \Rightarrow 111q_31*0 \Rightarrow 1111q_3*0 \Rightarrow \\ & \Rightarrow 1111*q_30 \Rightarrow 1111q_1*0 \Rightarrow 1111q_000. \end{aligned}$

Предлагается проверить самостоятельно, что данная машина Тьюринга осуществляет следующие преобразования конфигураций:

$\begin{gathered}11*q_11 \Rightarrow 111q_00; \qquad 111q_11 \Rightarrow 11111q_00;\\ 11*11q_11 \Rightarrow 11111q_00;\\ \qquad 11111*1q_11 \Rightarrow 1111111q_00.\end{gathered}$

Нетрудно заметить, что данная машина Тьюринга реализует операцию сложения: в результате ее работы на ленте записано подряд столько единиц, сколько их было всего записано по обе стороны от звездочки перед началом работы машины.

Этот маленький опыт работы с машинами Тьюринга позволяет сделать некоторые выводы. Так тщательно описанное устройство этой машины (разбитая на ячейки лента, считывающая головка) по существу не имеет никакого значения. Машина Тьюринга — не что иное, как некоторое правило (алгоритм) для преобразования слов алфавита $A\cup Q$ , т. е. конфигураций. Таким образом, для определения машины Тьюринга нужно задать ее внешний и внутренний алфавиты, программу и указать, какие из символов обозначают пустую ячейку и заключительное состояние.

Конструирование машин Тьюринга

Создание (синтез) машин Тьюринга (т.е. написание соответствующих программ) является задачей значительно более сложной, нежели процесс применения данной машины к данным словам.

Пример 32.3. Попытаемся построить такую машину Тьюринга, которая из $n$ записанных подряд единиц оставляла бы на ленте $n-2$ единицы, также записанные подряд, если $n \geqslant 2$ , и работала бы вечно, если $n=0$ или $n=1$ .

В качестве внешнего алфавита возьмем двухэлементное множество $A=\{0;1\}$ . Количество необходимых внутренних состояний будет определено в процессе составления программы. Считаем, что машина начинает работать из стандартного начального положения, т.е. когда в состоянии $q_1$ обозревается крайняя правая единица из $n$ записанных на ленте.

Начнем с того, что сотрем первую единицу, если она имеется, перейдем к обозрению следующей левой ячейки и сотрем там единицу, если она в этой ячейке записана. На каждом таком переходе машина должна переходить в новое внутреннее состояние, ибо в противном случае будут стерты вообще все единицы, записанные подряд. Вот команды, осуществляющие описанные действия:

$q_11\to q_20L;\quad q_21\to q_30L.$

Машина находится в состоянии $q_3$ и обозревает третью справа ячейку из тех, в которых записано данное слово ( $n$ единиц). Не меняя содержимого обозреваемой ячейки, машина должна остановиться, т.е. перейти в заключительное состояние $q_0$ , независимо от содержимого ячейки. Вот эти команды:

$q_30\to q_00;\quad q_31\to q_01.$

Теперь остается рассмотреть ситуации, когда на ленте записана всего одна единица или не записано ни одной. Если на ленте записана одна единица, то после первого шага (выполнив команду $q_11\to q_20L$ ) машина будет находиться в состоянии $q_2$ и будет обозревать вторую справа ячейку, в которой записан 0. По условию, в таком случае машина должна работать вечно. Это можно обеспечить, например, такой командой: $q_20\to q_20\Pi$ , выполняя которую шаг за шагом, машина будет двигаться по ленте неограниченно вправо (или протягивать ленту через считывающую головку справа налево). Наконец, если на ленте не записано ни одной единицы, то машина, по условию, также должна работать вечно. В этом случае в начальном состоянии $q_1$ обозревается ячейка с содержимым 0, и вечная работа машины обеспечивается следующей командой: $q_10\to q_10\Pi$ .

Запишем составленную программу (функциональную схему) построенной машины Тьюринга в виде таблицы:

$\begin{array}{|c|c|c|c|} \hline A \setminus Q & q_1 & q_2 & q_3 \\ \hline 0 & q_10\Pi & q_20\Pi & q_00\\ \hline 1& q_00L & q_20L & q_01 \\ \hline \end{array}$

В заключение отметим следующее. Созданная нами машина Тьюринга может применяться не только к словам в алфавите $A=\{0;1\}$ , представляющим собой записанные подряд п единиц $(n \geqslant 2)$ . Она применима и ко многим другим словам в этом алфавите, например (проверьте самостоятельно) к словам: 1011, 10011, 111011, 11011, 1100111, 1001111, 10111, 10110111, 10010111 и т.д. (исходя из стандартного начального положения). С другой стороны, построенная машина не применима (т.е. при подаче этих слов на вход машины она работает вечно) не только к слову "1" или к слову, состоящему из одних нулей. Она не применима и к следующим словам (проверьте самостоятельно): 101, 1001, 11101, 101101, 1100101101 и т.д..

Вычислимые по Тьюрингу функции

Определение 32.4. Функция называется вычислимой по Тьюрингу, если существует машина Тьюринга, вычисляющая ее, т.е. такая машина Тьюринга, которая вычисляет ее значения для тех наборов значений аргументов, для которых функция определена, и работающая вечно, если функция для данного набора значений аргументов не определена.

Остается договориться о некоторых условностях для того, чтобы это определение стало до конца точным. Во-первых, напомним, что речь идет о функциях (или возможно о частичных функциях, т. е. не всюду определенных), заданных на множестве натуральных чисел и принимающих также натуральные значения. Во-вторых, нужно условиться, как записывать на ленте машины Тьюринга значения хи $x_1,x_2,\ldots,x_n$ аргументов функции $f(x_1,x_2,\ldots,x_n)$ , из какого положения начинать переработку исходного слова и, наконец, в каком положении получать значение функции. Это можно делать, например, следующим образом. Значения $x_1,x_2,\ldots,x_n$ аргументов будем располагать на ленте в виде следующего слова:

$0\; \underbrace{1\,\ldots\,1}_{x_1}\; 0\; \underbrace{1\,\ldots\,1}_{x_2}\; 0\,\ldots\,0\; \underbrace{1\,\ldots\,1}_{x_n}\;0.$

Здесь полезно ввести следующие обозначения. Для натурального $x$ обозначаем:

$1^x= \underbrace{1\,\ldots\,1}_{x},\quad 0^x= \underbrace{0\,\ldots\,0}_{x}.$

Дополнительно полагаем $0^0=1^0=\Lambda$ — пустое слово. Так что на слова $1^0=\Lambda,1^1=1,1^2=11,1^3=111,\ldots$ будем смотреть как на "изображения" натуральных чисел $0,1,2,3\ldots$ соответственно. Таким образом, предыдущее слово можно представить следующим образом: $01^{x_1}01^{x_2}0\ldots01^{x_n}0$ . Далее, начинать переработку данного слова будем из стандартного начального положения, т.е. из положения, при котором в состоянии $q_1$ обозревается крайняя правая единица записанного слова. Если функция $f(x_1,x_2,\ldots,x_n)$ определена на данном наборе значений аргументов, то в результате на ленте должно быть записано подряд $f(x_1,x_2,\ldots,x_n)$ единиц; в противном случае машина должна работать бесконечно. При выполнении всех перечисленных условий будем говорить, что машина Тьюринга вычисляет данную функцию. Таким образом, сформулированное определение 35.4 становится абсолютно строгим.

Обратимся к примерам. Нетрудно понять, что машина Тьюринга из примера 32.2 по существу вычисляет функцию $f(x)=x+1$ , а машина Тьюринга из примера 32.3 вычисляет функцию $f(x)=x-2$ .

Пример 32.5. Построим машину Тьюринга, вычисляющую функцию $f(x)=x\slash2$ . Эта функция не всюду определена: областью ее определения является лишь множество всех четных чисел. Поэтому, учитывая определение 32.4, нужно сконструировать такую машину Тьюринга, которая при подаче на ее вход четного числа давала бы на выходе половину этого числа, а при подаче нечетного — работала бы неограниченно долго.

Сконструировать машину Тьюринга — значит написать (составить) ее программу. В этом процессе два этапа: сначала создается алгоритм вычисления значений функции, а затем он записывается на языке машины Тьюринга (программируется).

В качестве внешнего алфавита возьмем двухэлементное множество $A\{0;1\}$ . В этом алфавите натуральное число х изображается словом $11\ldots1$ , состоящим из $x$ единиц, которое на ленте машины Тьюринга записывается в виде $x$ единиц, стоящих в ячейках подряд. Работа машины начинается из стандартного начального положения: $01\ldots1q_110$ (число единиц равно $x$ ).

Сделаем начало вычислительного процесса таким: машина обозревает ячейки, двигаясь справа налево, и каждую вторую единицу превращает в 0. Такое начало обеспечивается следующими командами:

$\begin{aligned}&(1)\colon\quad q_11\to q_21L;\\ &(2)\colon\quad q_21\to q_10L;\\ &(3)\colon\quad q_20\to q_20L. \end{aligned}$

Если число $x$ единиц нечетно, то машина продолжит движение по ленте влево неограниченно, т.е. будет работать бесконечно. Если же число $x$ единиц четно, то в результате выполнения команд создается конфигурация $q_10010101\ldots01010$ , в которой число единиц равно $x\slash2$ . Остается сдвинуть единицы так, чтобы между ними не стояли нули. Для осуществления этой процедуры предлагается следующий алгоритм. Будем двигаться по ленте вправо, ничего на ней не меняя, до первой единицы и перейдем за единицу. Передвижение осуществляется с помощью следующих команд:

$\begin{aligned}&(4)\colon\quad q_10\to q_30\Pi;\\ &(5)\colon\quad q_30\to q_30\Pi;\\ &(6)\colon\quad q_31\to q_41\Pi. \end{aligned}$

В результате их выполнения получим конфигурацию

$001q_4010101\ldots010100.$

(*)

Заменим 0, перед которым остановились, на 1 и продвинемся вправо до ближайшего 0:

$\begin{aligned}&(7)\colon\quad q_40\to q_51\Pi;\\ &(8)\colon\quad q_51\to q_51\Pi. \end{aligned}$

Получим конфигурацию $00111q_50101\ldots010100$ , в которой правее обозреваемой ячейки записаны "пары" $01,\ldots,01$ . Кроме того, на ленте одна единица записана лишняя. Продвинемся по ленте вправо до последней "пары" $01$ . Это можно сделать с помощью своеобразного цикла:

$\begin{aligned}(9)\colon\quad &q_50\to q_60\Pi;\\ (10)\colon\quad &q_61\to q_51\Pi. \end{aligned}$

Получим конфигурацию $001110101\ldots01010q_600$ . Двигаться дальше вправо бессмысленно. Вернемся на две ячейки назад и заменим единицу из последней "пары" $01$ на ноль:

$\begin{aligned}(11)\colon\quad &q_60\to q_70L;\\ (12)\colon\quad &q_70\to q_70L; \\ (13)\colon\quad &q_71\to q_80L. \end{aligned}$

Получим конфигурацию $001110101\ldots01q_800$ . Число единиц на ленте снова равно $x\slash2$ . Продвинемся влево на одну ячейку с помощью команды

$(14)\colon\quad q_80\to q_90L.$

В результате чего получим конфигурацию $001110101\ldots010q_9100$ . Теперь уничтожим самую правую единицу и продвинемся по ленте влево до следующей единицы:

$\begin{aligned}& (15)\colon\quad q_91\to q_{10}0L;\\ & (16)\colon\quad q_{10}0\to q_{10}0L. \end{aligned}$

Получим конфигурацию

$001110101\ldots0q_{10}100,$

(**)

в которой левее обозреваемой ячейки записана серия пар $10,10,\ldots,10$ (если читать справа налево). Теперь на ленте недостает одной единицы, т.е. число единиц равно $(x\slash2)-1$ . Продвинемся по ленте влево до последней "пары" $10$ . Это можно сделать с помощью цикла

$\begin{aligned}& (17)\colon\quad q_{10}1\to q_{11}1L;\\ & (18)\colon\quad q_{11}0\to q_{10}0L, \end{aligned}$

выполнив который, придем к следующей конфигурации: $001q_{11}110101\ldots 0100$ . Вернемся вправо к ближайшему нулю и превратим его в единицу:

$\begin{aligned}& (19)\colon\quad q_{11}1\to q_{12}1\Pi;\\ & (20)\colon\quad q_{12}1\to q_{12}1\Pi;& (21)\colon\quad q_{12}0\to q_{13}1\Pi. \end{aligned}$

Получим конфигурацию $001111q_{13}101\ldots0100$ , в которой число единиц снова равно $x\slash2$ .

Если теперь перешагнем вправо по ленте через обозреваемую единицу и переведем машину в состояние $q_4$ с помощью команды

$(22)\colon\quad q_{13}1\to q_{4}1\Pi,$

то придем к следующей конфигурации: $0011111q_401\ldots0100$ , которая по существу аналогична конфигурации (*). В результате программа зацикливается (становится циклической): снова ближайший 0 превращается в 1, а самая правая 1 — в 0, затем машина возвращается к самому левому нулю, оказываясь в начале следующего цикла, и т.д.

Как же завершается работа программы? В некоторый момент конфигурация будет иметь вид $00111\ldots1110q_{10}100$ . Выполнив команды (17), (18), придем к конфигурации $00111\ldots1q_{11}110100$ . Далее выполняются команды (19), (20), (21), что приводит к конфигурации: $00111\ldots111111q_{13}00$ . Остается остановить машину. Это делается с помощью команды

$(23)\colon\quad q_{13}0\to q_{0}0L.$

Заключительная конфигурация имеет вид: $00111\ldots1111q_0100$ .

Запишем программу машины Тьюринга в табличной форме:

$\begin{array}{|c|c|c|}\hline Q \setminus A & 0 & 1\\ \hline q_{1} & q_{3}0\Pi & q_{2}1L\\ q_{2} & q_{2}0L & q_{1}0L\\ q_{3} & q_{3}0\Pi & q_{4}1\Pi\\ q_{4} & q_{5}1\Pi & \\ q_{5} & q_{6}0\Pi & q_{5}1\Pi\\ q_{6} & q_{7}0L & q_{5}1\Pi\\ q_{7} & q_{7}0L & q_{8}0L\\ q_{8} & q_{9}0L & q_{2}1L\\ q_{9} & & q_{10}0L\\ q_{10} & q_{10}0L & q_{11}1L\\ q_{11} & q_{10}0L & q_{12}1\Pi\\ q_{12} & q_{13}1\Pi & q_{13}1\Pi\\ q_{13} & q_{0}0L & q_{4}1\Pi\\ \hline \end{array}$

Предлагается самостоятельно проследить за работой этой машины Тьюринга, взяв в качестве исходных конкретные слова: 111, 1111, 111111, 1111111111.

Правильная вычислимость функций на машине Тьюринга

В предыдущем пункте мы рассмотрели вопрос о том, что значит и каким образом "данная машина Тьюринга вычисляет функцию $f(x_1,x_2,\ldots,x_n)$ ". Для этого нужно, чтобы каждое из чисел $x_1,x_2,\ldots,x_n$ было записано на ленту машины непрерывным массивом из соответствующего числа единиц, а сами массивы были разделены символом 0. Если функция $f(x_1,x_2,\ldots,x_n)$ определена на данном наборе значений аргументов, то в результате на ленте должно быть записано подряд $f(x_1,x_2,\ldots,x_n)$ единиц. При этом мы не очень строго относились к тому, в каком начальном положении машина начинает работать (часто это было стандартное начальное положение), в каком завершает работу и как эта работа протекает.

В дальнейшем нам понадобится более сильное понятие вычислимости функции на машине Тьюринга — понятие правильной вычислимости.

Определение 32.6. Будем говорить, что машина Тьюринга правильно вычисляет функцию $f(x_1,x_2,\ldots,x_n)$ , если начальное слово $q_101^{x_1}01^{x_2}0\ldots 01^{x_n}0$ она переводит в слово $q_001^{f(x_1,x_2,\ldots,x_n)}0\ldots0$ и при этом в процессе работы не пристраивает к начальному слову новых ячеек на ленте ни слева, ни справа. Если же функция $f$ не определена на данном наборе значений аргументов, то, начав работать из указанного положения, она никогда в процессе работы не будет надстраивать ленту слева.

Пример 32.7. Приведем программы машин Тьюринга, правильно вычисляющих функции $S(x)=x+1$ и $O(x)=0$ . Функция $S(x)=x+1$ осуществляет перевод: $q_101^x0 \Rightarrow q_001^{x+1}$ . Ее программа:

$q_10\to q_2\Pi,\quad q_21\to q_21\Pi,\quad q_20\to q_31,\quad q_31\to q_31L,\quad q_30\to q_00.$

Функция $O(x)=0$ осуществляет перевод: $q_101^x0 \Rightarrow q_000^{x+1}$ . Ее программа:

$q_10\to q_20\Pi,\quad q_21\to q_21\Pi,\quad q_20\to q_30L,\quad q_31\to q_40,\quad q_40\to q_30L,\quad q_30\to q_00$

Соответствующую машину Тьюринга обозначили $\rm{O}$ .

Пример 32.8. Построить две машины "левый сдвиг" $B^{-}$ и "правый сдвиг" $B^{+}$ . Первая из начального стандартного положения перерабатывает слово $01^x0$ в то же самое слово и останавливается, обозревая самую левую ячейку с нулем. Вторая машина из начального состояния, в котором обозревается левая ячейка с нулем, слово $01^x0$ перерабатывает в то же самое слово и останавливается, обозревая самую правую ячейку с нулем.

Программа машины $B^{-}\colon\, q_10\to q_20L,q_21\to q_21L,q_20\to q_00$ . Ясно, что программа машины $B^{+}$ получается из программы предыдущей машины заменой символа "L" символом "П".

Композиция машин Тьюринга

Определение 32.9. Пусть заданы машины Тьюринга $\Theta_1$ и $\Theta_2$ , имеющие общий внешний алфавит $\{a_0,a_1,\ldots,a_m\}$ и алфавиты внутренних состояний $\{q_0,q_1,\ldots,q_n\}$ и $\{q_0,q'_1,\ldots,q'_n\}$ соответственно. Композицией (или произведением) машины $\Theta_1$ на машину $\Theta_2$ называется новая машина $\Theta$ с тем же внешним алфавитом $\{a_0,a_1,\ldots,a_m\}$ , внутренним алфавитом $\{q_0,q_1,\ldots,q_n,q_{n+1},\ldots,q_{n+t}\}$ и программой, получающейся следующим образом. Во всех командах из $\Theta_1$ содержащих символ остановки $q_0$ , заменяем последний на $q_{n+1}$ . Все остальные символы в командах из $\Theta_1$ остаются неизменными. В командах из $\Theta_2$ символ $q_0$ оставляем неизменным, а все остальные состояния $q'_i\,(i=1,\ldots,t)$ заменяем соответственно на $q_{n+i}$ . Совокупность всех так полученных команд образует программу машины-композиции $\Theta$ .

Введенное понятие является удобным инструментом для конструирования машин Тьюринга. Покажем это на примере.

Пример 32.10. Сконструируем машины Тьюринга, правильно вычисляющие функции-проекторы $I_m^n(x_1,x_2,\ldots,x_n)=x_m$ $(1 \leqslant m \leqslant n)$ .

Рассмотрим сначала конкретный случай $n=2,n=3$ , т.е. функцию $I_2^3(x_1, x_2,x_3)=x_2$ . Мы должны переработать слово $q_101^{x_1}01^{x_2}01^{x_3}0$ в слово $q_001^{x_2}0$ . Будем применять к начальной конфигурации последовательно сконструированные ранее машины Тьюринга $B^{+},V,B^{-},\rm{O}\colon$ .

$\begin{aligned}& & & q_101^{x_1}01^{x_2}01^{x_3}0;\\ &B^{+}\colon & & 01^{x_1}q01^{x_2}01^{x_3}0;\\ &V\colon & & 01^{x_2}q01^{x_1}01^{x_3}0;\\ &B^{+}\colon & & 01^{x_2}01^{x_1}q01^{x_3}0;\\ &\rm{O}\colon & & 01^{x_2}01^{x_1}q00^{x_3}0 ;\\ &B^{-}\colon & & 01^{x_2}q01^{x_1}00^{x_3}0;\\ &\rm{O}\colon & & 01^{x_2}q00^{x_1}00^{x_3}0;\\ &B^{-}\colon & & q01^{x_2}00^{x_1}00^{x_3}0.\end{aligned}$

Таким образом, функция $I_2^3(x_1,x_2,x_3)=x_2$ вычисляется следующей композицией машин:

$B^{+}VB^{+}\rm{O}B^{-}\rm{O}B^{-}=B^{+}VB^{+}(\rm{O}B^{-})^2.$

Проверьте самостоятельно, что функция $I_2^2(x_1,x_2)=x_2$ вычисляется композицией $B^{+}V\rm{O}B^{-}$ .

Теперь мы можем представить себе алгоритм построения композиции машин $B^{+},V, B^{-},\rm{O}$ для вычисления любой функции вида $I_m^n(x_1,x_2,\ldots,x_n)= x_m$ с помощью правого сдвига $B^{+}$ , применив его $m-1$ раз, нужно сначала достичь массива $01^{x_m}$

$(B^{+})^{m-1}\colon\quad 01^{x_1}0\ldots q01^{x_m}0\ldots01^{x_n}0.$

Затем, двигаясь влево, транспонировать (с помощью $V$ ) массив $01^{x_m}$ с каждым соседним слева массивом, пока массив $01^{x_m}$ не выйдет на первое место:

$(V\cdot B^{-})^{m-1}\colon\quad q01^{x_m}01^{x_1}0\ldots 01^{x_{m-1}} 01^{x_{m+1}}0\ldots 01^{x_n}0.$

Теперь нужно дойти до крайнего правого массива с помощью (n-1)-кратного применения правого сдвига $B^{+}\colon$

$(B^{+})^{n-1}\colon\quad 01^{x_m}01^{x_1}0\ldots 01^{x_{m-1}}01^{x_{m+1}}0\ldots q01^{x_n}0.$

Наконец, нужно стирать последовательно справа налево все массивы единиц, кроме первого:

$(\rm{O}B^{-})^{n-1}\colon\quad q01^{x_{m}}00^{x_{1}}0\ldots 00^{x_{m-1}} 00^{x_{m+1}}0\ldots 00^{x_{n}}0.$

Итак, данную функцию (правильно) вычисляет следующая машина Тьюринга:

$(B^{+})^{m-1} (V\cdot B^{-})^{m-1} (B^{+})^{n-1} (\rm{O}\cdot B^{-})^{n-1}.$

При $n=3,m=2$ эта машина имеет вид:

$B^{+}VB^{-}(B^{+})^2(\rm{O}B^{-})^2= B^{+}VB^{+}(\rm{O}B^{-})^2,$

т.е. совпадает с построенной выше машиной. При $n=2,m=2$ эта машина имеет вид: $B^{+}(VB^{-})B^{+}(\rm{O}B^{-})= B^{+}V\rm{O}B^{-}$ , т.е. также совпадает с соответствующей рассмотренной выше машиной Тьюринга.

Тезис Тьюринга (основная гипотеза теории алгоритмов)

Вернемся к интуитивному представлению об алгоритмах. Напомним, одно из свойств алгоритма заключается в том, что он представляет собой единый способ, позволяющий для каждой задачи из некоего бесконечного множества задач за конечное число шагов найти ее решение.

На понятие алгоритма можно взглянуть и с несколько иной точки зрения. Каждую задачу из бесконечного множества задач можно выразить (закодировать) некоторым словом некоторого алфавита, а решение задачи — каким-то другим словом того же алфавита. В результате получим функцию, заданную на некотором подмножестве множества всех слов выбранного алфавита и принимающую значения в множестве всех слов того же алфавита. Решить какую-либо задачу — значит найти значение этой функции на слове, кодирующем данную задачу. А иметь алгоритм для решения всех задач данного класса — значит иметь единый способ, позволяющий в конечное число шагов "вычислять" значения построенной функции для любых значений аргумента из ее области определения. Таким образом, алгоритмическая проблема — по существу, проблема о вычислении значений функции, заданной в некотором алфавите.

Остается уточнить, что значит уметь вычислять значения функции. Это значит вычислять значения функции с помощью подходящей машины Тьюринга. Для каких же функций возможно их тьюрингово вычисление? Многочисленные исследования ученых, обширный опыт показали, что такой класс функций чрезвычайно широк. Каждая функция, для вычисления значений которой существует какой-нибудь алгоритм, оказывалась вычислимой посредством некоторой машины Тьюринга. Это дало повод Тьюрингу высказать следующую гипотезу, называемую основной гипотезой теории алгоритмов, или тезисом Тьюринга:

Для нахождения значений функции, заданной в некотором алфавите, тогда и только тогда существует какой-нибудь алгоритм, когда функция является вычислимой по Тьюрингу, т. е. когда она может вычисляться на подходящей машине Тьюринга.

Это означает, что строго математическое понятие вычислимой (по Тьюрингу) функции является по существу идеальной моделью взятого из опыта понятия алгоритма. Данный тезис есть не что иное, как аксиома, постулат, выдвигаемый нами, о взаимосвязях нашего опыта с той математической теорией, которую мы под этот опыт хотим подвести. Конечно же данный тезис в принципе не может быть доказан методами математики, потому что он не имеет внутриматематического характера (одна сторона в тезисе — понятие алгоритма — не является точным математическим понятием). Он выдвинут исходя из опыта, и именно опыт подтверждает его состоятельность. Точно так же, например, не могут быть доказаны и математические законы механики; они открыты Ньютоном и многократно подтверждены опытом.

Впрочем, не исключается принципиальная возможность того, что тезис Тьюринга будет опровергнут. Для этого должна быть указана функция, которая вычислима с помощью какого-нибудь алгоритма, но невычислима ни на какой машине Тьюринга. Но такая возможность представляется маловероятной (в этом одно из значений гипотезы): всякий алгоритм, который будет открыт, может быть реализован на машине Тьюринга.

Дополнительные косвенные доводы в подтверждение этой гипотезы будут приведены в двух последующих параграфах, где рассматриваются другие формализации интуитивного понятия алгоритма и доказывается их равносильность с понятием машины Тьюринга.

Машины Тьюринга и современные электронно-вычислительные машины

Изучение машин Тьюринга и практика составления программ для них закладывают фундамент алгоритмического мышления, сущность которого состоит в том, что нужно уметь разделять тот или иной процесс вычисления или какой-либо другой деятельности на простые составляющие шаги. В машине Тьюринга расчленение (анализ) вычислительного процесса на простейшие операции доведено до предельной возможности: распознавание единичного рассмотренного вхождения символа, перемещение точки наблюдения данного ряда символов в соседнюю точку и изменение имеющейся в памяти информации. Конечно, такое мелкое дробление вычислительного процесса, реализуемого в машине Тьюринга, значительно его удлиняет. Но вместе с тем логическая структура процесса, расчлененного, образно выражаясь, до атомарного состояния, значительно упрощается и предстает в некотором стандартном виде, весьма удобном для теоретических исследований. (Именно такое расчленение на простейшие составляющие вычислительного процесса на машине Тьюринга дает еще один косвенный аргумент в пользу тезиса Тьюринга, обсуждавшегося в предыдущем пункте: всякая функция, вычисляемая с помощью какого-либо алгоритма, может быть вычислена на машине Тьюринга, потому что каждый шаг данного алгоритма можно расчленить на еще более мелкие операции, которые реализуются в машине Тьюринга.) Таким образом, понятие машины Тьюринга есть теоретический инструмент анализа алгоритмического процесса, а значит, анализа существа алгоритмического мышления.

В современных ЭВМ алгоритмический процесс расчленен не на столь мелкие составляющие, как в машинах Тьюринга. Наоборот, создатели ЭВМ стремятся к известному укрупнению выполняемых машиной процедур (на этом пути, конечно, есть свои ограничения). Так, для выполнения операции сложения на машине Тьюринга составляется целая программа, а в современной ЭВМ такая операция является простейшей.

Далее, машина Тьюринга обладает бесконечной внешней памятью (неограниченная в обе стороны лента, разбитая на ячейки). Но ни в одной реально существующей машине бесконечной памяти быть не может. Это говорит о том, что машины Тьюринга отображают потенциальную возможность неограниченного увеличения объема памяти современных ЭВМ.

Наконец, можно провести более подробный сравнительный анализ работы современной ЭВМ и машины Тьюринга. В большинстве ЭВМ принята трехадресная система команд, обусловленная необходимостью выполнения бинарных операций, в которых участвует содержимое сразу трех ячеек памяти. Например, число из ячейки $a$ умножается на число из ячейки $b$ , и результат отправляется в ячейку $c$ . Существуют ЭВМ двухадресные и одноадресные. Так, одноадресная ЭВМ работает следующим образом: вызывается (в сумматор) число из ячейки $a$ ; в сумматоре происходит, например, умножение этого числа на число из ячейки $b$ ; результат отправляется из сумматора в ячейку $c$ . Машину Тьюринга можно считать одноадресной машиной, в которой система одноадресных команд упрощена еще больше: на каждом шаге работы машины команда предписывает замену лишь единственного знака, хранящегося в обозреваемой ячейке, а адрес обозреваемой ячейки при переходе к следующему такту может меняться лишь на единицу (обозрение соседней справа или слева ячейки ленты) или не меняться вовсе. Это удлиняет процесс, но в то же время резко унифицирует его, делает стандартным.

Подводя итоги, можно сказать, что современные ЭВМ есть некие реальные физические модели машин Тьюринга, огрубленные с точки зрения теории, но созданные в целях реализации конкретных вычислительных процессов. В свою очередь, понятие машины Тьюринга и теория таких машин есть теоретический фундамент и обоснование современных ЭВМ.

Математический форум (помощь с решением задач, обсуждение вопросов по математике).

Если заметили ошибку, опечатку или есть предложения, напишите в комментариях.

Список статей » Список форумов

Часовой пояс: UTC + 3 часа [ Летнее время ]