Понятие частично-рекурсивных функций оказалось исчерпывающей формализацией понятия вычислимой функции. Это обстоятельство выражено тезисом Черча: всякая функция, вычислимая некоторым алгоритмом, частично-рекурсивна.
Это утверждение – аналог тезиса Тьюринга (Всякий алгоритм может быть реализован машиной Тьюринга) для рекурсивных функций. Из сопоставления этих двух тезисов вытекает следующее утверждение: функция вычислима машиной Тьюринга тогда и только тогда, когда она частично-рекурсивна.
Итак, всякий алгоритм, описанный в терминах частично-рекурсивных функций можно реализовать машиной Тьюринга и наоборот. Отсюда следует, что любые утверждения о существовании или несуществовании алгоритмов, сделанные в одной из этих теорий, верны и в другой.
Ввиду инвариантности основных результатов общей теории алгоритмов прикладное значение ее результатов не связано с тем, насколько близки к практике используемые в ней модели алгоритмов.
Машины Тьюринга весьма далеки от современной ЭВМ, а рекурсивные функции – от языков программирования. Однако, именно скромность используемых средств делает эти модели удобным языком доказательств, и позволяет понять без чего обойтись нельзя, а без чего можно и какой ценой: т.е. отличать удобства от принципиальных возможностей.
Что такое тезис Чёрча-Тьюринга? Душкин объяснит
Теория рекурсивных функций являясь частью теории алгоритмов, представляет собой разветвленную математическую дисциплину с собственной проблематикой и с приложениями в других разделах математики. Цель теории рекурсивных функций – это исчерпать все мыслимые функции, поддающиеся вычислению с помощью какой-нибудь процедуры механического характера.
Тезис Черча не может быть доказан строго математически, он подтверждается практикой. Все рассматривавшиеся в математике конкретные функции, признаваемые вычислимыми в интуитивном смысле, оказывались рекурсивными.
6.2.6 Проблема самоприменимости
Множество всех алгоритмов счетно. Это означает наличие взаимно-однозначного соответствия между алгоритмами и числами натурального ряда, т.е. функции типа
j: Al® N
Такая функция называется нумерацией алгоритмов, а ее значение j(А) – номером алгоритма А при нумерации j. Из взаимной однозначности отображения j следует, что существует обратная функция j -1 (n)= Аn, восстанавливающая по номеру n описание алгоритма Аn.
Очевидно, что различных нумераций много. Существование нумераций позволяет работать с алгоритмами как с числами. Это удобно при исследовании алгоритмов над алгоритмами. Такие алгоритмы уже рассматривались при построении универсальной машины Тьюринга и в связи с проблемой остановки. По существу, вычислимая умерация служит языком программирования для универсального алгоритма.
Теорема 6.1. Не существует алгоритма В(x,y) такого, что для любого алгоритма Аx (с номером j(А)=х)
Иначе говоря, не существует алгоритма, который по номеру х любого алгоритма и исходным данным y определял бы остановится алгоритм Ах при этих данных или нет.
Дискра Билет 8 (Машина Тьюринга, параметризация и рекурсия)
Теорема 6.2. Проблема самоприменимости алгоритмов аналитически неразрешима.
Т.е. не существует алгоритма В1(х) такого, что для любого Ах
Эти две теоремы являются мощным средством для доказательства разных неразрешимостей.
Решение задачи перечисления всех алгоритмов (в частности, всех рекурсивных функций) в принципе ясно. Может показаться, что перечисление примитивно-рекурсивных или общерекурсивных функций окажется более легким делом.
Теорема 6.3. Для любого перечисления любого множества всюду определенных вычислимых (т.е. общерекурсивных) функций существует общерекурсивная функция не входящая в это перечисление.
Если в перечислении допускаются частичные функции, то определение В не приводит к противоречию, а лишь означает, что в точке Хв функция В(Хв) не определена.
Теорема 6.4. Проблема определения общерекурсивности алгоритмов неразрешима.
Не существует алгоритма В(х) такого, что для любого алгоритма Ах
Среди требований к алгоритмам говорилось о желательности такого требования, как результативность. Первым ударом по этому требованию была неразрешимость проблемы остановки, означающая, что если алгоритм может быть частичным, то по алгоритму А и данным х нельзя узнать, даст А результат на данных х или нет.
Возникает естественное желание либо вообще убрать частичные алгоритмы из общей теории алгоритмов (скажем, не считать их ал-горитмами), либо ввести стандартный метод доопределения частичных алгоритмов. Однако ни то, ни другое эффективными методами сделать нельзя. В силу последней теоремы нет эффективного способа распознавать частичные алгоритмы среди множества всех алгоритмов и следовательно, предполагаемый отбор невозможен. Что касается второй идеи, для нее существует не менее убедительное опровержение:
Теорема 6.5. Существует такая частично-рекурсивная функция f, что никакая общерекурсивная функция g не является ее доопределением.
Следовательно, существуют частичные алгоритмы, которые нельзя доопределить до всюду определенного алгоритма.
Еще одна идея: построить язык, описывающий все всюду определенные алгоритмы и только их. Осуществить ее нельзя потому, что описания в этом языке можно упорядочить и следовательно, наличие такого языка означало бы существование полного перечисления всех всюду определенных функций, что противоречит теореме 3.
Таким образом, возникает дилемма: либо определение алгоритма должно быть достаточно общим, чтобы в число объектов, удовлетворяющих этому определению заведомо вошли все объекты, которые естетственно считать алгоритмами, либо требование об обязательной результативности сохраняется.
Просматривая весь запас алгоритмически неразрешимых проблем, можно заметить, что все они так или иначе связаны с самоприменимостью. Понятие самоприменимости весьма далеко от алгоритмической практики, следовательно, можно предположить, что и неразрешимость в этой практике никогда не встречается.
Теорема Райса. Никакое нетривиальное свойство вычислимых функций не является алгоритмически разрешимым.
Отсюда следует, что по номеру вычислимой функции нельзя узнать, является ли эта функция постоянной, периодической, ограниченной и т.д.
Чтобы разобраться в смысле теоремы Райса, следует вспомнить, что номер х функции f – это номер алгоритма Ах, вычисляющего f; по номеру алгоритма однозначно восстанавливается его описание, и разным номерам соответствуют разные алгоритмы.
Для функций это неверно: при x¹y fx и fy могут быть одной и той же функцией ( в ее классическом смысле).
Можно ли по тексту сколько-нибудь сложной программы (не запуская ее в работу) понять, что она делает ( не имея гипотез о том, что она должна делать)? В этом тексте алгоритмическим путем можно отыскать так называемые синтаксические ошибки – те или иные свойства описания алгоритма (и это делают трансляторы и компиляторы с алгоритмических языков программирования).
Хорошо известно, что в процессе отладки программ синтаксические ошибки обнаруживаются очень быстро; все неприятности связаны с анализом семантики программы, т.е. с попытками установить, что же собственно программа делает, вместо того, чтобы делать задуманное.
Тезис Черча-Тьюринга: основные понятия, определение, вычислимые функции, значение и применение
Тезис Черча-Тьюринга относится к понятию эффективного, систематического или механического метода в логике, математике и информатике. Он формулируется как описание интуитивного понятия вычислимости и в отношении к общерекурсивным функциям чаще называется тезисом Черча. Он также относится к теории вычислимых при помощи компьютеров функций. Тезис появился в 1930-х годах, когда самих компьютеров еще не существовало. Позднее он был назван в честь американского математика Алонсо Черча и его британского коллеги Алана Тьюринга.
Эффективность метода достижения результата
Первым устройством, напоминавшим современный компьютер, была Bombie — машина, созданная английским математиком Аланом Тьюрингом. Она использовалась для расшифровки немецких сообщений во время Второй мировой войны. Но для своего тезиса и формализации понятия алгоритма он использовал абстрактные машины, впоследствии названные машинами Тьюринга. Тезис представляет интерес, как для математиков, так и для программистов, так как эта идея вдохновила создателей первых компьютеров.
В теории вычислимости тезис Черча-Тьюринга также известен как гипотеза о природе вычислимых функций. Он гласит, что для любой алгоритмически вычислимой функции на натуральных числах существует машина Тьюринга, способная ее вычислить. Или, другими словами, есть подходящий для нее алгоритм. Хорошо известным примером эффективности этого метода является тест-таблицы истинности для проверки тавтологичности.
Способ для достижения какого-либо желаемого результата называется «эффективным», «систематическим» или «механическим», если:
- Метод задается в терминах конечного числа точных команд, каждая инструкция выражается при помощи конечного числа символов.
- Он будет выполняться без ошибок, приведет к желаемому результату за определенное число шагов.
- Метод может выполняться человеком без посторонней помощи любым оборудованием, кроме бумаги и карандаша
- Он не требует понимания, интуиции или изобретательности со стороны человека, осуществляющего действия
Ранее в математике использовался неофициальный термин «эффективно вычислимый», чтобы обозначить функции, которые можно вычислить при помощи карандаша и бумаги. Но само понятие алгоритмической вычислимости было скорее интуитивным, чем чем-то конкретным. Теперь же оно характеризовалось функцией с натуральным аргументом, для которой существует алгоритм вычисления. Одним из достижений Алана Тьюринга было представление формально точного предиката, при помощи которого можно было бы заменить неформальный, если использовать условие эффективности метода. Черч сделал то же самое открытие.
Основные понятия рекурсивных функций
Замена предикатов, предложенная Тьюрингом, на первый взгляд выглядела отличной от той, что предложил его коллега. Но в результате они оказались эквивалентными, в том смысле, что каждый из них выбирает один и тот же набор математических функций. Тезис Черча-Тьюринга является утверждением, что это множество содержит каждую функцию, значения которой могут быть получены методом, удовлетворяющим условиям эффективности. Было еще одно отличие этих двух открытий. Оно заключалось в том, что Черч рассматривал только примеры положительных целых чисел, тогда как Тьюринг описывал свою работу как охватывающую вычислимые функции с интегральной или реальной переменной.
Общие рекурсивные функции
В первоначальной формулировке Черча говорится, что расчет может быть выполнен с использованием λ-исчисления. Это эквивалентно использованию общих рекурсивных функций. Тезис Черча-Тьюринга охватывает больше видов вычислений, чем те, которые изначально предполагались. Например, связанные с клеточными автоматами, комбинаторами, регистрационными машинами и системами замещения.
В 1933 году математики Курт Гедель и Жаком Хербранд создали формальное определение класса, называемого общими рекурсивными функциями. Оно использует функции, в которых возможен более чем один аргумент.
Создание метода λ-исчисления
В 1936 году Алонсо Черч создал метод определения, называемых λ-исчислением. Он был связан с натуральными числами. Внутри λ-исчисления ученый определил их кодирование. В результате они получили название чисел Черча. Функция на основе натуральных чисел называлась λ-вычислимой.
Было и другое определение. Функция из тезиса Черча называется λ-вычислимой при двух условиях. Первое звучало так: если она была рассчитана на элементах Черча, а вторым условием была возможность представления членом λ-исчисления.
Также в 1936 году, прежде чем изучать работу своего коллеги, Тьюринг создал теоретическую модель для абстрактных машин, теперь называемых его именем. Они могли бы выполнять вычисления путем манипулирования символами на ленте. Это также относится к другим математическим действиям, найденным в теоретической информатике, таким как квантовые вероятностные вычисления. Функция из тезиса Черча только впоследствии была обоснована с применением машины Тьюринга. Изначально они опирались на λ-исчисления.
Вычислимость функции
При подходящем кодировании натуральных чисел в виде последовательностей символов функция на натуральных чисел называется вычислимой по версии Тьюринга, если абстрактная машина находила нужный алгоритм и выводила эту функцию на ленте. Подобное устройство, которого не существовало в 1930-х, в будущем стали считать компьютером.
Абстрактная машина Тьюринга и тезис Черча стали предвестниками эры развития вычислительных устройств. Было доказано, что формально определенные обоими учеными классы функций совпадают. Потому в результате оба утверждения объединили в одно. Вычислительные функции и тезис Черча также оказали сильное влияние на концепцию вычислимости. А также стали важным подспорьем для математической логики и теории доказательств.
Обоснование и проблемы метода
Существуют противоречивые точки зрения на тезис. Многочисленные доказательства были собраны для «рабочей гипотезы», предложенной Черчем и Тьюрингом в 1936 году. Но все известные методы или операции для выявления новых эффективно вычисляемых функций из заданных были связаны с методами построения машин, которых тогда не существовало. Для того чтобы доказать тезис Черча-Тьюринга, исходят из того факта, что каждая реалистическая модель вычислений эквивалентна.
Из-за разнообразия различных анализов, как правило, это считается особенно убедительным доказательством. Все попытки более точно определить интуитивное понятия эффективно вычисляемой функции оказались эквивалентными. Каждый предложенный анализ доказал, что он выделяет один и тот же класс функций, а именно те, которые вычислимы машинами Тьюринга. Но некоторые вычислительные модели оказались более эффективны с точки зрения временных затрат и использования памяти для разных задач. Позднее отмечалось, что основные понятия рекурсивных функций и тезис Черча являются, скорее, гипотетическими.
«Тезис М»
Важно различать тезис Тьюринга и утверждение о том, что все, что может быть рассчитано вычислительным устройством, может быть рассчитано его машиной. У второго варианта есть свое собственное определение. Ганди называет второе предложение «Тезисом М». Он звучит так: «Независимо от того, что может быть вычислено устройством, можно вычислить машиной Тьюринга».
В узком понимании тезиса, он является эмпирическим предложением, истинностное значение которого неизвестно. Тезис Тьюринга и «Тезис М» иногда путают. Версия второго в широком смысле неверна. Были описаны различные условные машины, которые могут вычислять функции, не являющиеся вычислимыми по Тьюрингу. Важно обратить внимание, что первый тезис не влечет за собой второй, но согласуется с его ложностью.
Обратное имплицирование тезиса
В теории вычислимости тезис Черча используется как описание понятия вычислимости классом общерекурсивных функций. Американский Стивен Клини дал более общую формулировку. Он назвал частично рекурсивными все частичные функции, вычислимые при помощи алгоритмов.
Обратное имплицирование обычно называется обратным тезисом Черча. Он заключается в том, что каждая рекурсивная функция положительных целых чисел эффективно вычисляется. В узком смысле тезис просто обозначает такую возможность. А в широком — абстрагируется от вопроса о том, может ли существовать в нем эта условная машина.
Квантовые компьютеры
Понятия вычислимых функций и тезис Черча стали важным открытием для математики, теории машин и многих других наук. Но техника сильно изменилась и продолжает совершенствоваться. Предполагается, что квантовые компьютеры могут выполнять множество общих задач с меньшими временными затратами по сравнению с современными. Но остаются такие вопросы, как проблема с остановкой.
На нее квантовый компьютер не может ответить. И, согласно тезису Черча-Тьюринга, никакое другое вычислительное устройство тоже.
Источник: fb.ru
Предполагается, что универсальный исполнитель должен уметь доказывать существование или отсутствие алгоритма для той или иной задачи.
Т.о. можно дать формальное определение алгоритма по Тьюрингу. Машина Тьюринга — математический объект, и данное на ее основе определение алгоритма может использоваться для доказательства.
Примеры работы машины Тьюринга
Задача 1. 1
На ленте записано число в двоичной системе счисления. Каретка находится где-то над числом. Требуется увеличить число на единицу.
Чтобы решить задачу, нам нужно:
-определить алфавит машины Тьюринга А,
— определить набор состояний Q,
— составить программу (т.е. для каждой пары (аi,qi) определить команду автомата.)
Алфавит машины Тьюринга, работающей с двоичными цифрами будет включать цифры 0, 1 и пробел a0. Т.е. А=.
Определим возможные состояния:
1. q1 — автомат ищет правый конец слова (числа) на ленте
2. q2 — автомат увеличивает число на 1, проходя его слева направо и останавливается, закончив работу.
Напишем программу:
1 часть. q1 — автомат ищет правый конец слова (числа на ленте)
1)если в рабочей ячейке записано 0 — переместиться вправо
2)если в рабочей ячейке записано 1 — переместиться вправо
3) если в рабочей ячейке пробел, переместить каретку влево и перейти в состояние q2
Составим таблицу переходов для q1 т.о.:
| q1 | |
| 0 → q1 | |
| 1 → q1 | |
| a0 | a0 ← q2 |
2 часть. q2 — автомат увеличивает число на 1, проходя его слева направо и останавливается, закончив работу.
1) если в рабочей ячейке записана цифра 0, записать в нее 1 и стоп
2) если в рабочей ячейке записана цифра 1, выполнить перенос в старший разряд — записать в ячейку 0 и переместиться влево.
3) если в рабочей ячейке пробел, записать в нее 1 и стоп.
Добавим в нашу таблицу состояние q2:
| алфсостояния | q1 | q2 |
| 0 → q1 | 1. q0 | |
| 1 → q1 | 0 ← | |
| a0 | a0 ← q2 | 1. q0 |
Построенная таблица и есть программа для машины Тьюринга.
Обзор компонентов Multisim Компоненты – это основа любой схемы, это все элементы, из которых она состоит. Multisim оперирует с двумя категориями.
Композиция из абстрактных геометрических фигур Данная композиция состоит из линий, штриховки, абстрактных геометрических форм.
Важнейшие способы обработки и анализа рядов динамики Не во всех случаях эмпирические данные рядов динамики позволяют определить тенденцию изменения явления во времени.
ТЕОРЕТИЧЕСКАЯ МЕХАНИКА Статика является частью теоретической механики, изучающей условия, при которых тело находится под действием заданной системы сил.
Тактические действия нарядов полиции по предупреждению и пресечению групповых нарушений общественного порядка и массовых беспорядков В целях предупреждения разрастания групповых нарушений общественного порядка (далееГНОП) в массовые беспорядки подразделения (наряды) полиции осуществляют следующие мероприятия.
Механизм действия гормонов а) Цитозольный механизм действия гормонов. По цитозольному механизму действуют гормоны 1 группы.
Алгоритм выполнения манипуляции Приемы наружного акушерского исследования. Приемы Леопольда – Левицкого. Цель.
Оценка качества Анализ документации. Имеющийся рецепт, паспорт письменного контроля и номер лекарственной формы соответствуют друг другу. Ингредиенты совместимы, расчеты сделаны верно, паспорт письменного контроля выписан верно. Правильность упаковки и оформления.
БИОХИМИЯ ТКАНЕЙ ЗУБА В составе зуба выделяют минерализованные и неминерализованные ткани.
Типология суицида. Феномен суицида (самоубийство или попытка самоубийства) чаще всего связывается с представлением о психологическом кризисе личности.
Источник: studopedia.info