Никакое человеческое существо не способно писать достаточно быстро, достаточно долго или достаточно мелко1 для того, ... - Большая Энциклопедия Нефти и Газа



Выдержка из книги Булос Д.N. Вычислимость и логика


Никакое человеческое существо не способно писать достаточно быстро, достаточно долго или достаточно мелко1 для того, чтобы выписать одно за другим имена ( в некоторой системе обозначений) всех элементов некоторого счетно бесконечного множества. Но для некоторых счетно бесконечных множеств в человеческих силах сделать нечто равно полезное: можно сформулировать явные инструкции, позволяющие для произвольного п определять п-й элемент данного множества. Такие инструкции должны быть предельно четкими и иметь такую форму, чтобы им могла следовать вычислительная машина или же человек, способный к выполнению только очень элементарных операций над символами. Однако из соображений простоты и ясности мы игнорируем эти ограничения и будем, таким образом, работать с понятием вычислимости, превосходящим реальные возможности человека или машины. Главное - это чтобы наше понятие вычислимости не оказалось слишком узким, поскольку уже вскоре мы будем его использовать для доказательства невычислимости некоторых функций, а также того факта, что некоторые счетные множества не являются эффективно ( механически) перечислимыми - даже если разрешено каким-либо образом обходить физические ограничения на время, скорость и количество требующегося материала.

(cкачать страницу)

Смотреть книгу на libgen

Никакое человеческое существо не способно писать достаточно быстро, достаточно долго или достаточно мелко1 для того, чтобы выписать одно за другим имена ( в некоторой системе обозначений) всех элементов некоторого счетно бесконечного множества. Но для некоторых счетно бесконечных множеств в человеческих силах сделать нечто равно полезное: можно сформулировать явные инструкции, позволяющие для произвольного п определять п-й элемент данного множества. Такие инструкции должны быть предельно четкими и иметь такую форму, чтобы им могла следовать вычислительная машина или же человек, способный к выполнению только очень элементарных операций над символами. Однако из соображений простоты и ясности мы игнорируем эти ограничения и будем, таким образом, работать с понятием вычислимости, превосходящим реальные возможности человека или машины. Главное - это чтобы наше понятие вычислимости не оказалось слишком узким, поскольку уже вскоре мы будем его использовать для доказательства невычислимости некоторых функций, а также того факта, что некоторые счетные множества не являются эффективно ( механически) перечислимыми - даже если разрешено каким-либо образом обходить физические ограничения на время, скорость и количество требующегося материала.