Cтраница 3
В заключительной, четырнадцатой, главе впервые в этой книге вводятся бесконечные системы. Показано, что вещественные числа образуют несчетное множество. Определяется понятие вычислимости, объясняется его связь с машинами Тьюринга. Наконец, понятие машинной вычислимости связывается с некоторыми идеями математической лингвистики и проблемой классификации языков программирования. [31]
В понимании этих вроде бы очевидных вещей нужна определенна. Эта биективная функция непременно должна быть вычислимой ( относительно чего. Таким образом, понятие вычислимости неизбежно проникает уже в понятие системы записи чисел. [32]
Никакое человеческое существо не способно писать достаточно быстро, достаточно долго или достаточно мелко1 для того, чтобы выписать одно за другим имена ( в некоторой системе обозначений) всех элементов некоторого счетно бесконечного множества. Но для некоторых счетно бесконечных множеств в человеческих силах сделать нечто равно полезное: можно сформулировать явные инструкции, позволяющие для произвольного п определять п-й элемент данного множества. Такие инструкции должны быть предельно четкими и иметь такую форму, чтобы им могла следовать вычислительная машина или же человек, способный к выполнению только очень элементарных операций над символами. Однако из соображений простоты и ясности мы игнорируем эти ограничения и будем, таким образом, работать с понятием вычислимости, превосходящим реальные возможности человека или машины. Главное - это чтобы наше понятие вычислимости не оказалось слишком узким, поскольку уже вскоре мы будем его использовать для доказательства невычислимости некоторых функций, а также того факта, что некоторые счетные множества не являются эффективно ( механически) перечислимыми - даже если разрешено каким-либо образом обходить физические ограничения на время, скорость и количество требующегося материала. [33]
Как я отмечал ранее, существуют и другие способы определения понятия вычислимости. Несколько позже, но независимо от Тьюринга, Пост предложил во многом сходную концепцию вычислительной машины. Современные подходы к проблеме вычислимости ( такие как машина с неограниченным регистром, описанная Катлендом [ 198Q ]) в деталях значительно отличаются от разработанного Тьюрингом и более пригодны для практического использования. Однако понятие вычислимости во всех этих подходах остается неизменным. [34]
Если используется лента, то какая: имеющая начало, но не имеющая конца или же бесконечная с обеих сторон. В зависимости от того, какие ответы будут даны на эти вопросы, понятие вычисления, если говорить о деталях, приобретет тот или иной вид. Наша задача, однако, состоит вовсе не в том, чтобы дать точное изображение отдельных шагов, из которых складывается вычисление, и, более того, класс функций, допускающих вычисление, оказывается, не зависит от того, какие ответы будут получены на эти вопросы. Имеющийся опыт работы с понятием вычислимости наводит на мысль, что основное содержание этого понятия не зависит от того, какие - достаточно правдоподобные - ответы будут приняты. Действительно, если взять любое другое точное и правдоподобное определение понятия вычисления из тех, которые были предложены, то можно аккуратно и строго доказать, что наше понятие вычислимости эквивалентно новому в том смысле, что всякая функция, вычислимая согласно одному из них, оказывается вычислимой и согласно другому. Но так как нет предела возможным вариациям в точном определении понятий вычислимости и эффективности, то следует в конце концов принять или отвергнуть тезис ( не допускающий математического доказательства) о том, что множество функций, вычислимых в нашем смысле, совпадает с множеством функций, доступных для вычисления машинами и людьми с использованием произвольных эффективных методов, если только игнорируются ограничения, связанные с нужными временем, скоростью и материалом. Хотя этот тезис ( известный как тезис Черча) недоказуем, он был бы опровержимым, если бы оказался ложным. Действительно, если он ложен, то существует функция, вычислимая в интуитивном смысле, но не вычислимая с нашей точки зрения. [35]
Никакое человеческое существо не способно писать достаточно быстро, достаточно долго или достаточно мелко1 для того, чтобы выписать одно за другим имена ( в некоторой системе обозначений) всех элементов некоторого счетно бесконечного множества. Но для некоторых счетно бесконечных множеств в человеческих силах сделать нечто равно полезное: можно сформулировать явные инструкции, позволяющие для произвольного п определять п-й элемент данного множества. Такие инструкции должны быть предельно четкими и иметь такую форму, чтобы им могла следовать вычислительная машина или же человек, способный к выполнению только очень элементарных операций над символами. Однако из соображений простоты и ясности мы игнорируем эти ограничения и будем, таким образом, работать с понятием вычислимости, превосходящим реальные возможности человека или машины. Главное - это чтобы наше понятие вычислимости не оказалось слишком узким, поскольку уже вскоре мы будем его использовать для доказательства невычислимости некоторых функций, а также того факта, что некоторые счетные множества не являются эффективно ( механически) перечислимыми - даже если разрешено каким-либо образом обходить физические ограничения на время, скорость и количество требующегося материала. [36]
Существует большое разнообразие традиционных определений алгоритмов, ориентированных на тот или иной способ вычислений: функции, изобразимые в арифметическом исчислении предикатов ( К. Гедель, 1931), - определимые функции ( А. Фундаментальной логической основой теории алгоритмов является тот факт, что все эти определения эквивалентны в смысле возможности моделирования вычислений. В классической теории алгоритмов основной упор делается на понятие принципиальной вычислимости, а форма задания алгоритма особой роли не играет. Характерной особенностью традиционных определений алгоритма является выбор минимальных средств для представления и преобразования информации, продиктованный соображениями удобства формализации понятия алгоритма. Процедуры конкретных вычислений, записанные при помощи подобных минимальных средств, сводятся к сложной кодировке и моделированию преобразования информации и обычно настолько громоздки и затруднительны для понимания, что не могут быть использованы в реальной практике. [37]
Если используется лента, то какая: имеющая начало, но не имеющая конца или же бесконечная с обеих сторон. В зависимости от того, какие ответы будут даны на эти вопросы, понятие вычисления, если говорить о деталях, приобретет тот или иной вид. Наша задача, однако, состоит вовсе не в том, чтобы дать точное изображение отдельных шагов, из которых складывается вычисление, и, более того, класс функций, допускающих вычисление, оказывается, не зависит от того, какие ответы будут получены на эти вопросы. Имеющийся опыт работы с понятием вычислимости наводит на мысль, что основное содержание этого понятия не зависит от того, какие - достаточно правдоподобные - ответы будут приняты. Действительно, если взять любое другое точное и правдоподобное определение понятия вычисления из тех, которые были предложены, то можно аккуратно и строго доказать, что наше понятие вычислимости эквивалентно новому в том смысле, что всякая функция, вычислимая согласно одному из них, оказывается вычислимой и согласно другому. Но так как нет предела возможным вариациям в точном определении понятий вычислимости и эффективности, то следует в конце концов принять или отвергнуть тезис ( не допускающий математического доказательства) о том, что множество функций, вычислимых в нашем смысле, совпадает с множеством функций, доступных для вычисления машинами и людьми с использованием произвольных эффективных методов, если только игнорируются ограничения, связанные с нужными временем, скоростью и материалом. Хотя этот тезис ( известный как тезис Черча) недоказуем, он был бы опровержимым, если бы оказался ложным. Действительно, если он ложен, то существует функция, вычислимая в интуитивном смысле, но не вычислимая с нашей точки зрения. [38]
Если используется лента, то какая: имеющая начало, но не имеющая конца или же бесконечная с обеих сторон. В зависимости от того, какие ответы будут даны на эти вопросы, понятие вычисления, если говорить о деталях, приобретет тот или иной вид. Наша задача, однако, состоит вовсе не в том, чтобы дать точное изображение отдельных шагов, из которых складывается вычисление, и, более того, класс функций, допускающих вычисление, оказывается, не зависит от того, какие ответы будут получены на эти вопросы. Имеющийся опыт работы с понятием вычислимости наводит на мысль, что основное содержание этого понятия не зависит от того, какие - достаточно правдоподобные - ответы будут приняты. Действительно, если взять любое другое точное и правдоподобное определение понятия вычисления из тех, которые были предложены, то можно аккуратно и строго доказать, что наше понятие вычислимости эквивалентно новому в том смысле, что всякая функция, вычислимая согласно одному из них, оказывается вычислимой и согласно другому. Но так как нет предела возможным вариациям в точном определении понятий вычислимости и эффективности, то следует в конце концов принять или отвергнуть тезис ( не допускающий математического доказательства) о том, что множество функций, вычислимых в нашем смысле, совпадает с множеством функций, доступных для вычисления машинами и людьми с использованием произвольных эффективных методов, если только игнорируются ограничения, связанные с нужными временем, скоростью и материалом. Хотя этот тезис ( известный как тезис Черча) недоказуем, он был бы опровержимым, если бы оказался ложным. Действительно, если он ложен, то существует функция, вычислимая в интуитивном смысле, но не вычислимая с нашей точки зрения. [39]