Вычислимость

Cтраница 3

Фундаментальный результат, связывающий вычислимость по Тьюрингу с частично рекурсивными функциями и МНР-вычислимостью, состоит в следующем. [31]

Решение 1. Алгоритм. [32]

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

Но тогда предположение о вычислимости функции t по Тьюрингу ведет к противоречию ( без использования тезиса Черча) и потому является ложным. [34]

Как правило, требуется вычислимость функций размера. Тем не менее, есть исключения: например, колмогоровская сложность - невычислимая функция размера с очень важными свойствами ( см. ниже и разд. [35]

Другой способ вывести понятие вычислимости из систем Поста состоит в непосредственном моделировании вычислений машины. Это можно сделать, используя множества продукций Q, такие, что к любой данной цепочке применима самое большее одна продукция из Q. Однородная система действует последовательно подобно машине. [36]

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

Дальнейшее изучение теоретического понятия вычислимости ( отправной пункт рассмотрений этой книги) можно продолжить в двух направлениях: ( а) более подробное исследование других эквивалентных подходов к вычислимости ( обзор которых был дан в гл. [38]

Это подсказывает способ доказательства вычислимости по Тьюрингу вычислимой по Геделю функции. [39]

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

Если отвлечься от понятия вычислимости, то действительные числа называются действительными, потому что они, как представляется, дают величины, необходимые для измерения расстояний, углов, времени, энергии, температуры и многих других геометрических и физических параметров. Однако связь абстрактно определенных действительных чисел с физическими величинами не так проста, как может показаться. Действительные числа следует рассматривать скорее как некоторую математическую идеализацию, чем как реальную меру физически объективных величин. Система действительных чисел обладает, например, таким свойством, что между любыми двумя действительными числами ( вне зависимости от их близости) существует третье действительное число. При этом совершенно не ясно, можно ли обоснованно утверждать то же самое о физических расстояниях или промежутках времени. Если мы продол -, жим дробить физическое расстояние между двумя точками, то мы в конце концов достигнем масштабов столь малых, что само понятие расстояния в обычном его смысле станет бессмысленным. Предполагается, что это действительно имеет место на масштабах, характерных для квантовой теории гравитации, которые в 1020 раз2) меньше размеров субатомных частиц. Но чтобы отобразить действительные числа нам потребуется дойти до сколь угодно более мелких масштабов, которые, например, в 10200, Ю2000 или даже в Ю10 раз меньше размеров частиц. И совершенно не ясно, есть ли какой бы то ни было физический смысл у столь абсурдно малых масштабов. [41]

В этом разделе мы рассмотрим вычислимость относительно m - полного перечислимого множества. Любые два таких множества m - сводятся друг к другу, и тем более Т - сводятся друг к другу. Поэтому если какая-то функция вычислима относительно одного из них, то она вычислима и относительно другого. Такие функции называют О1 - вычислимыми. [42]

В настоящее время начали изучать вычислимость при определенных ограничивающих предположениях о доступных вычислительных ресурсах: например, что осуществимо при ограничениях, наложенных на продолжительность вычислений или на объем доступной памяти. [43]

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

Особое внимание следует обратить на вычислимость критерия надежности. [45]

Страницы: 1 2 3 4