Машина  Тьюринга является абстрактным вычислительным устройством, к которому могут быть сведены все существующие компьютеры. Она состоит из читающей/пишущей головки и длинной ленты. Головка может считывать символы с ленты и записывать их на ленту. На каждом шаге машина может решить, что делать дальше следуя очень простой программе, включающей команды условного перехода, команды чтения/записи и сдвиги ленты. Лента может быть сколь угодно длинная для того, чтобы мы могли решить данную проблему, но она не должна быть бесконечной, и это ключевой момент. Если проблема может быть решена, то она может быть решена на машине Тьюринга, имеющей конечную ленту. Именно машина Тьюринга используется для иллюстрации того, является ли тот или иной алгоритм выполнимым за конечное время, в конечном пространстве. Если она не может этого сделать, алгоритм не выполним.

      Разрешимость

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

      Квантовое поведение

“Кубит” -  это квантовый бит, который можно рассматривать так же как и цифровой бит в компьютере, за исключением одного важного различия. Хотя в цифровом компьютере бит может принимать лишь значения 0 или 1, кубит может иметь значения 0,1 или же оба одновременно. Я объясню, что это означает, но сначала я расскажу, как кубит может быть создан.

Мы  можем сконструировать кубит, используя  атом некоторого элемента - возьмем  для примера водород. Атом водорода состоит из ядра (которое нас не интересует) и орбитального электрона. Этот электрон может существовать на различных энергетических уровнях, или орбиталях вокруг ядра. Эти различные орбитали могут использоваться для представления бинарных значений 0 и 1, которые известны нам по цифровым компьютерам. Мы могли бы предположить, например, что атом водорода в основном состоянии (т.е. в состоянии, в котором электрон находится ближе всего к ядру)   представляет собой значение 0. Подобным же образом, мы можем сказать, что атом, электрон которого находится на первом возбужденном уровне представляет значение 1. Для перевода электрона с одного уровня возбуждения на другой мы можем воздействовать на него поляризованным излучением лазера - по существу мы вводим в нашу систему фотоны. Как только они инжектируются, электрон начинает переходить с одного уровня энергии на другой. Так что, для того чтобы перевернуть бит из 0 в 1 мы просто облучаем атом достаточным количеством света так, чтобы электрон перешел на более высокий энергетический уровень. Для того чтобы перевести 1 в 0, мы делаем то же самое, так как перегрузка электрона приведет к переходу его назад в основное состояние. Логически это эквивалентно действию вентиля NOT, т.е. одной из тех операций, которые требуются нам в компьютере для вычислений. Используя аналогичные идеи, мы можем сконструировать вентили AND и COPY, которые вместе с вентилем NOT составляют три основные компоненты вычислительного устройства.

До  сих пор мы не видели качественного  различия между использованием обычных  битов и кубитов, но нечто странное происходит, если мы облучаем атом светом, которого достаточно лишь для того, чтобы электрон проделал половину пути между уровнями возбуждения. Поскольку электроны  не могут в действительности существовать в пространстве между этими уровнями, они существуют НА ОБОИХ уровнях одновременно. Это известно как “суперпозиция”.  Эта суперпозиция позволяет нам теоретически вычислить одновременно несколько возможностей , так как группа кубитов может представлять одновременно несколько чисел. Если мы возьмем один “кубайт”, то есть 8 кубитов, то мы сможем одновременно представить 256 чисел. С числом кубитов количество представимых чисел растет по закону , где n- число кубитов.

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

Итак, действительный вопрос здесь в том  можно ли получить с помощью описанного квантового вычисления нечто еще  не достигнутое с помощью обычных классических компьютеров? Ответ, конечно, положительный. Квантовое вычисление обеспечивает громадное преимущество по скорости. Рассмотрим задачу, которая требует исключительно большого времени вычислений на классическом компьютере, такую как факторизация 250-значного числа. По имеющейся оценке 1400 параллельно работающих современных компьютеров решат ее примерно за 800 000 лет. Даже если будут разработаны более производительные компьютеры, и мы найдем пути лучшего интегрирования широкомасштабного параллелизма, проблема все еще останется  экспоненциально сложной. Однако, для квантового компьютера сложность проблемы будет полиномиальной по времени , а не экспоненциальной. Например, 1000-значное число можно будет факторизовать лишь за несколько миллионов шагов.  Основная вера связана здесь с тем, что, используя параллельную природу квантовых явлений (т.е. суперпозицию), мы сможем вычислять все возможности параллельно.

Однако, это не философский камень вычисления. Квантовое вычисление, по крайней  мере, в имеющейся форме, НЕ позволяет вычисления чего-либо более сложного, нежели то, что может быть осуществлено на обычном классическом компьютере. Объем задачи, которую мы можем решить, ограничено числом используемых кубитов, и мы не можем решать задачи без остановки через необходимо конечное время. В этом отношении квантовый компьютер не более чем быстрая машина Тьюринга. По сути, дело в том, что квантовый компьютер все еще остается подвластен ограничениям тезиса Черча Тьюринга. Существует пара исключительно сумасшедших теорий о том, как их можно обойти, но я поговорю о них в конце моего выступления.

Справедлив  ли тезис Черча-Тьюринга для всех квантовых компьютеров не совсем ясно. Квантовые вычисления, о которых  мы говорили до сих пор, осуществляются очень сходным образом с действием обычных компьютеров (т.е. с использованием битов, логических вентилей, памяти и т.п.), но не существует прямых доводов полагать, что это означает невозможность разработки других типов квантовых вычислений, которые являются существенно более мощными. Одной из таких моделей может быть квантовая нейронная сеть. Хотя возможно построить квантовую нейронную сеть, используя кубиты и т.п., как это описано выше, это было бы эквивалентно конструированию обычной нейронной сети на классической машине, и  обеспечило бы преимущества перед обычной нейронной сетью только по скорости, но не по вычислимости. Если мы хотим сконструировать квантовую нейронную  сеть, не ограниченную тезисом Черча-Тьюринга, мы должны подумать о радикально ином подходе к кубитам и логическим вентилям. Это конечно очень трудно, и до сих пор серьезных попыток в данном направлении не предпринималось. Хотя некоторые предложения, которые могут служить началом поиска нового типа квантовых вычислений,  действительно существуют.

      Обход  ограничений тезиса Черча-Тьюринга

Ранее я отметил, что существует ряд  странных теорий относительно того, как  можно было бы использовать квантовый  компьютер для реализации алгоритмов существенно более сложных, чем  те, которые разрешимы машиной  Тьюринга. Держим в уме, что они носят в высшей степени спекулятивный характер (что, как я предполагаю в любом случае относится ко всей области квантовых вычислений). Проведение вычислений, не имеющих конечного состояния (т.е. неразрешимого алгоритма) не могло бы быть возможным как на классическом, так и на имеющихся моделях квантового компьютера.  Например, доказательство гипотезы Гольдбаха путем одновременной проверки всех случаев. Гипотеза Гольдбаха  формулируется следующим образом “Каждое четное число может быть представлено в виде суммы двух простых чисел”. Можно было бы написать алгоритм (который не имеет остановки) для решения этой проблемы, который просто берет каждое четное число и перебирает натуральные числа до нахождения двух его простых нечетных слагаемых. Если бы мы могли использовать этот алгоритм бесконечное время, то смогли бы найти нечетные слагаемые всех четных чисел. Конечно, это невозможно на машине Тьюринга,  поскольку в этом случае алгоритм не имеет остановки. И поскольку квантовый компьютер вычислительно эквивалентен  машине Тьюринга, он также не способен найти ответ.

Одно  из интересных решений этой проблемы предполагает использование норы червяка².Если мы создадим замкнутый ход червяка и используем его как часть нашего квантового компьютера, то мы могли бы иметь бесконечное время необходимое для вычисления ответа, просто проводя вычисление в замкнутой бесконечной петле. Другое предложение состоит в расширении чевячного хода в то что известно как  ‘basement universe’ - существенно новый мир внутри нашего собственного - а затем создание другого мира внутри уже созданного и так до бесконечности. Если мы создадим эти миры используя эффект замедления времени (в согласии с общей теории относительности), тогда бы мы смогли выполнять каждое действие несколько быстрее, чем в мире-родителе. Все что мы должны бы были сделать далее, это скопировать наш квантовый компьютер из этих миров в их потомков и т.д. и это вернет результат бесконечно долгого вычисления за конечное время, фактически мгновенно.

 Согласно недавно предложенной космологической теории  вселенная может породить потомка, который возникает вначале в виде некоторой неоднородности (выпуклости) и преобразуется в некое подобие  протуберанца, связанного с материнской вселенной узкой пуповиной, которая и называется норой червяка (wormhole). Из вселенной-родителя она выглядит как черная дыра. Эта пуповина, утончаясь, может порваться (что будет выглядеть как испарение черной дыры), и тогда вселенная-потомок отделится от материнской. Согласно теории советского физика Андрея Линде  наш мир образовался именно таким образом, как маленький пузырек пространства-времени, который расширился в ходе того, что мы называем Большим Взрывом.

      Глава 2. Практическая часть.

      Заключение.

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

Легко понять, что любая примитивно рекурсивная функция является частично рекурсивной, так как по определению операторы для построения частично рекурсивных функций включают в себя операторы для построения примитивно рекурсивных функций.

Также понятно, что примитивно рекурсивная функция определена везде и поэтому является общерекурсивной функцией (у примитивно рекурсивной функции нет повода «зависать», так как при её построении используются операторы, определяющие везде определённые функции).

Тезис Чёрча — Тьюринга невозможно строго доказать или опровергнуть, поскольку он устанавливает эквивалентность между строго формализованным понятием частично вычислимой функции и неформальным понятием вычислимости.

Люди  иногда задаются таким вопросом: «  А что если ты докажешь этот тезис, что если опровергнешь? Голодающие станут сытыми, обездоленные получат лучшую жизнь, а войны прекратятся?»

Нет, просто я думаю, что человечество продвинется на шаг вперед в научной  сфере. Сейчас, конечно, ты начнешь " обстрел ", а какая с этого  польза и так далее. Отвечу сразу: тебе этого просто не понять. Не потому что ты глупый, а просто потому что я чувствую, что это нужно. Ведь, как говориться, чем меньше мы знаем, тем легче нам жить. Такие люди, которые думают “ а зачем все это, что с этого будет и т.п. ” были, есть и будут всегда. Именно поэтому сожгли Джордано Бруно на костре, просто потому что церковь не могла понять, какая будет польза с того что он делал. Может сейчас в данный момент от этого пользы "0". А может через лет 100-200 доказательство этого тезиса перевернет понимания кибернетики, как таковой.

      Литература:

• Мальцев А. И., Алгоритмы и рекурсивные функции, М., 1965 ;
• Роджерс Х., Теория рекурсивных функций и эффективная вычислимость, пер. с англ., М., 1972 ;
• http://dic.academic.ru ;
• http://ru.wikipedia.org .