Cтраница 1
Понятие вычислимости по Маркову очень похоже на понятие вычислимости по Посту, полученное вторым способом из предыдущего параграфа. Однако вместо того, чтобы ограничиться рассмотрением однородных систем, Марков приводит правила, позволяющие однозначно определять, какую из имеющихся продукций применить следующей. [1]
С понятием вычислимости естественным образом связываются понятия истинной и ложной формулы, а также понятие верифицируемой формулы. Нумерическое равенство будет называться истинным, если в результате вычисления всех входящих в него функций обе его части принимают одно и то же значение. [2]
Другой способ вывести понятие вычислимости из систем Поста состоит в непосредственном моделировании вычислений машины. Это можно сделать, используя множества продукций Q, такие, что к любой данной цепочке применима самое большее одна продукция из Q. Однородная система действует последовательно подобно машине. [3]
Все те несколько попыток формализовать понятие вычислимости привели к понятиям, которые ( формально) эквивалентны вычислимости по Тьюрингу. Среди них - понятие лямбда-определимости, разработанное Черчем, и понятие общей рекурсивности, введенное Геделем. [4]
Как и для функций, понятие вычислимости последовательности перечислимых множеств может быть определено двояко: можно считать вычислимой последовательность VoVi... V, а можно требовать, чтобы по t можно было алгоритмически указать один из номеров г - го члена последовательности в главной нумерации. [5]
Когда Вальд писал свою статью, понятие вычислимости было лишь недавно создано, и А. [6]
Теперь мы можем дать точное определение понятия отно сительной вычислимости, пользуясь видоизмененным вариантом нашей МНР, который называется Машиной с неограниченными регистрами и оракулом, или сокращенно МНРО. [7]
Бели такой метод существует, то тьюрингово понятие вычислимости оказывается слишком узким: в этом случае существуют вычислимые функции, не являющиеся вычислимыми по Тьюрингу, и, в частности, такова функция и. Бели же тьюрингово понятие вычислимости достаточно широко, чтобы охватить все функции, вычислимые хоть в каком-либо интуитивном смысле, то сформулированная проблема оказывается неразрешимой. [8]
Понятие вычислимости по Маркову очень похоже на понятие вычислимости по Посту, полученное вторым способом из предыдущего параграфа. Однако вместо того, чтобы ограничиться рассмотрением однородных систем, Марков приводит правила, позволяющие однозначно определять, какую из имеющихся продукций применить следующей. [9]
Как писал американский математик Эмиль Пост, понятие вычислимости может сыграть в истории дискретной математики роль, уступающую по значению лишь понятию натурального числа. [10]
Рациональное число является конструктивным объектом, так что понятие вычислимости не требует специального уточнения. [11]
Как я отмечал ранее, существуют и другие способы определения понятия вычислимости. Несколько позже, но независимо от Тьюринга, Пост предложил во многом сходную концепцию вычислительной машины. [12]
Это воистину замечательный факт, который подчеркивает глубоко объективный и математичный характер понятия вычислимости. На первый взгляд, понятие вычислимости по Черчу не связано с вычислительными машинами. И тем не менее, оно имеет непосредственное отношение к практическим аспектам вычислений. В частности, мощный и гибкий язык программирования LISP включает в себя как существенный элемент основные структуры исчисления Черча. [13]
Еще одна родственная проблема, подобным же образом оказывающаяся неразрешимой, если только тьюрингово понятие вычислимости универсально, - это проблема остановки из упр. Тьюринга ( неважно, в стандартной или в какой-либо иной заключительной конфигурации), если ее запустить в начальном ее состоянии считывающей самую левую клетку в сплошном массиве единиц на ленте с пустыми символами во всех остальных клетках. Замечательно, что независимо от того, принимается тезис Черча или нет, следующая функция Л, вычислимость которой в интуитивном смысле эквивалентна разрешимости проблемы остановки, оказывается, как можно доказать, невычислимой по Тьюрингу: Л ( тп, п) 2 или 1 в соответствии с тем, остановится в конце концов или нет машина Тьюринга с номером т, если ее запустить в начальном состоянии считывающей самую левую единицу в сплошном блоке из п единиц на ленте с пустыми символами во всех остальных клетках. Таким образом, если тезис Черча верен, то проблема остановки неразрешима. [14]
В этом параграфе рассматривается определение Маркова, разбираются некоторые примеры и выясняется связь между понятиями вычислимости и нормальной вычислимости. [15]