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