Чего не могут вычислительные машины

Исходный вариант статьи (Н. Н. Непейвода, «Чего не могут вычислительные машины?») опубликован в журнале «Потенциал».

С точки зрения системного анализа в нашей жизни происходит не компьютерная революция, а компьютерная контрреволюция.

Г. Вейценбаум. «Возможности вычислительных машин и человеческий разум»

Прежде чем пытаться что-то запрограммировать, полезно оценить осмысленность и осуществимость задачи. Чтобы оценивать, нужно понимать. Понимание невозможно без знания, но знание не всегда даёт понимание. Понимания можно достичь, лишь когда знаешь также и пределы своего знания.

Эта статья посвящается принципиальным ограничениям алгоритмического подхода.

Машина Тьюринга

Вы часто можете встретить в литературе утверждение, что некоторый алгоритмический язык либо система универсальны, то есть позволяют запрограммировать всё, что угодно. Но часто слово «универсальный» употребляется неточно, скорее для восхваления^[1]. В программировании же это слово определено строго.

Как известно, программирование появилось раньше вычислительных машин. Первым программистом был Чарлз Бэббидж, ибо он написал программы для своей, опять же, первой в истории, вычислительной машины^[2]. Точно так же теория программирования в самой своей основе появилась раньше первой программно-управляемой машины Конрада Цузе. Цузе прекрасно знал теорию и строил свои системы отнюдь не на пустом месте.

Из философских побуждений — неудовлетворённости квазирелигиозной верой в истинность математических утверждений, необоснованность которой стала тогда очевидной — в течение почти всего XX века упорно разрабатывалась метаматематика, то есть исследование математики средствами самой математики. Одним из итогов этого развития стала математическая логика, а другим — теория алгоритмов.

Самые различные понятия вычислимости и определимости были исследованы с той поры, когда в 1920-х гг. появились первые уточнения понятия алгоритма. Зачастую кажется, что в них нет ничего общего.

Знаменитая машина Тьюринга была построена Аланом Тьюрингом исходя из общих философских соображений как формализация работы человека по точно определённому предписанию над чётко заданными исходными сведениями. Алан Тьюринг сделал несколько весьма общих предположений. Перечислим их в несколько вольном изложении.

Во-первых, если информация точная, то её элементарные единицы должны быть чётко различимы между собой.
Во-вторых, человек даже в принципе может распознать лишь конечное число единиц элементарной информации (даже если восприятие его столь мощно, что он единым взором охватывает целый лист, всё равно на этом листе может поместиться лишь конечное число символов).
В-третьих, все замены, которые он делает в качестве элементарного шага, могут рассматриваться как замены одной единицы информации на другую (написал новый лист вместо старого).
В-четвёртых, хотя в хранилище информации может храниться сколько угодно единиц информации, прямой переход возможен лишь к соседней единице. Это предположение наименее тривиально на первый взгляд и поэтому оказалось наиболее содержательным.
И, наконец, сам ум человека может принимать лишь конечное число состояний, поскольку иначе некоторые из них были бы неразличимы между собой.

В итоге получается следующая условная модель. Память представляет собой потенциально бесконечную ленту, разбитую на ячейки. В каждой ячейке может храниться символ из заранее ограниченного конечного набора символов (алфавита). Если, скажем, рассматривать в качестве такой ячейки машинное слово, то символов будет $2^{32}$ штук. Процессор представляет собой головку, передвигающуюся по ленте. В процессоре записана матрица из конечного числа команд, каждая из которых по отдельности обрабатывает все возможные символы (так что для рассмотренного нами случая ширина такой матрицы команд будет $2^{32}$ ). Опознав символ, машина может записать на его место другой символ, сдвинуться на одну ячейку в любую из сторон и перейти к другой команде. Данная модель и называется машиной Тьюринга.

Например, следующая матрица даёт машину с пятью состояниями и тремя входными воздействиями для весьма нетривиальной задачи — добавление единицы к двоичному числу, записанному на ленте, начиная со старшего разряда.

Обозреваемый символ		0	1	B
Начало	a	cR0	bR1	aRB
Перенос	b	cR0	bR1	dLB
Нет переноса	c	cR0	bR1	eLB
Назад с переносом	d	eL1	dL0	0S1
Назад без переноса	e	eL0	eL1	0SB

В каждой клетке таблицы первый символ задаёт новое состояние машины, R, L, S помечают, в какую сторону движется головка по ленте (вправо, влево, стоит на месте), третий символ — новый символ, который будет записан в текущую ячейку ленты. Когда машина переходит в состояние 0, она останавливается.

А следующая простенькая машина с семью состояниями и чытырьмя входными воздействиями (взятая из книги Минский М. Вычисления и автоматы. М: Мир, 1971, с.331) является ‘’универсальной’’ и моделирует любую другую машину Тьюринга.

	1	2	3	4	5	6	7
y	0L1	0L1	yL3	yL4	yR5	yR6	0R7
0	0L1	yR2	0S0	yR5	yL3	AL3	yR6
1	1L2	AR2	AL3	1L7	AR5	AR6	1R7
A	1L1	yR6	1L4	1L4	1R5	1R6	0R2

Отметим, что структура это таблицы отличается от структуры предыдущей таблицы.

Разобраться в том, как она это делает, может лишь законченный хакер высокого класса. Есть и более простые конструкции универсальной машины, но они намного длиннее.

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

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

При этом вначале строится какая-либо простая змейка в пространстве, проходящая через все его «кубики», подобно тому, как изображённая на рисунке спираль обходит все клетки плоскости, а дальше машина Тьюринга ходит по одномерной ленте, но понимает её как эту змейку. Конечно же, число шагов и сложность самой машины при этом возрастают, но с теоретической точки зрения это неважно.

Так что, когда теоретик Вам говорит, что нечто в Принципе можно сделать, почти всегда нужно понимать его «В теории можно, а на практике вряд ли!».

Точно так же можно иметь несколько одновременно работающих головок. Если разрешить вставлять и удалять ячейки под головкой, то и это моделируется обычной машиной. А обычная машина может быть смоделирована такой, у которой всего две головки, лента пустая, за исключением маркера начала ленты, головки могут лишь двигаться, но не писать, и не могут передвигаться левее маркера начала, либо такой машиной с одной головкой, которая может лишь записывать 1 вместо 0, но не может стирать однажды написанную единицу. Результатом при этом считается номер клетки, на которой остановилась первая головка.

Но, конечно же, можно ослабить и так, что понятие на самом деле ослабится. Для этого достаточно, скажем, превратить рабочую ленту в ‘’ магазин’’, стирая прочитанный символ, если мы сдвигаемся левее его. Так что, в этом случае все рабочее пространство заключено между началом ленты и текущим положением головки, и доступен лишь последний из записанных в этом пространстве символов.

Далее, если ввести две различные ленты: одну лишь для чтения, а другую лишь для записи, причём чтение и запись необратимы (после такой операции мы принудительно сдвигаемся вправо), то получается понятие ‘’ конечного автомата’’, существенно более слабое, чем машина Тьюринга. В частности, наша первая сложная машина делает то, что не может сделать конечный автомат. Конечный автомат может прибавить 1 к двоичному числу лишь в том случае, если число подаётся, начиная с младшего разряда.

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

В общем, это один из многочисленных случаев, когда практик зачастую слишком тупо понимает теоретика, а потом обвиняет его в своей глупости. Чуть-чуть подумав, можно понять, что теоретическая эквивалентность означает свободу выбора конкретного представления для практика, а не безразличие к выбору представления. Ответственность за выбранное конкретное представление лежит, конечно же, целиком на практике. А ответственность за то, чтобы предоставить ему как можно более широкий и разнообразный выбор в идеальной системе взаимодействия теории и практики должна была бы лежать на теоретике, прежде всего, на профессоре, обучающем студентов.

Именно обогащение набора различных представлений данных является причиной, по которой хороший курс алгебры даёт программисту намного больше, чем 100 курсов по конкретным системам представления данных.).

Тезис Чёрча

Другие системы представления алгоритмов чаще всего принципиально отличаются от машин Тьюринга. Например, гениальная до безумия система комбинаторной логики петербургского математика Л. Шейнфинкеля (исторически первое точное понятие алгоритма) имеет две элементарных операции S и K с мистически выглядящим определением:

$Kxy=x$

$Sxyz=xz(yz)$

Рекурсивные схемы Маккарти полностью отказываются от локальности действий, переходя к системе функциональных описаний, подобных

f(x)\gets {\mbox{ if }}\ P(x)\ {\mbox{ then }}\ x\ {\mbox{ else }}\ f(f(h(x)))\ {\mbox{ fi}}.

Алгоритмы Колмогорова-Успенского работают над графовыми структурами, машины Поста выглядят как до предела упрощённая система команд компьютера и так далее.

Уже к концу 1930-х гг. выяснилось, что столь разные понятия алгоритма приводят к одному и тому же множеству определимых функций, и был сформулирован тезис Чёрча (Алонзо Черч— американский логик, один из основателей, в частности, теории алгоритмов):

Все алгоритмы эквивалентны между собой с точностью до вычислимой кодировки и, в конечном счёте, эквивалентны машинам Тьюринга.

Уровень подтверждённости тезиса Чёрча к настоящему времени гораздо выше уровня подтверждённости любого так называемого «естественнонаучного закона», но математики скромно называют его «тезисом», потому что он в принципе не может быть строго доказан. По-прежнему тезис проверяется для всех вновь появляющихся понятий алгоритма. Сбоев нет и не предвидится.

Тезис Чёрча перестаёт, вообще говоря, работать, если мы рассматриваем относительную вычислимость (наш алгоритм может пользоваться некоторой данной нам библиотекой стандартных функций). В этом случае рекурсивные схемы одно из самых мощных средств программирования (как и можно было предполагать содержательно), а машина Тьюринга — одно из самых строгих. Это уже известное ограничение области действия тезиса Чёрча ещё повышает степень его достоверности.

Неразрешимость

Раз, в принципе, все можно сделать на машине Тьюринга, то эта машина служит удобным инструментом для того, чтобы показать, что на ней сделать ‘’нельзя’’. Тогда это нельзя сделать и на самом навороченном языке типа С++ (но представьте себе безумца, который пытался бы показать, что нечто нельзя сделать на этом монстре, не пользуясь теоретическими понятиями!). Но прежде всего нужно уточнить термины.

Машина применима к исходным данным, если она на них останавливается. Разрешимым свойством называется такое, для которого можно построить программу, его проверяющую. Формализуя данное определение, мы получаем следующее:

Разрешимое свойство — такое, для которого есть всегда останавливающаяся машина Тьюринга, выдающая в качестве конечного результата либо 0, либо 1.

Множество объектов называется разрешимым, если есть алгоритм, который получает на вход объект и определяет, принадлежит объект этому множеству или нет. Такой алгоритм обязан остановиться при любом объекте на входе, то есть быть всюду определённым.

В теории алгоритмов устанавливается, что существует универсальный алгоритм, перерабатывающий пару (программа, входные данные) в результат работы соответствующей программы (один из его вариантов приведён выше).

Более того, реализациями идеи универсального алгоритма вы все время пользуетесь. Это транслятор с С++, интерпретатор Java и даже сама по себе система команд машины.

Мы подошли к важнейшему достижению науки ХХ в.: понятию неразрешимой задачи, которое проиллюстрируем сейчас на примере понятия неразрешимого свойства.

Теорема 1

Неразрешимо свойство «Машина Тьюринга ${\mathfrak {M}}$ останавливается, будучи запущенной на данных $X$ » Таким образом, если нетривиальное функциональное свойство программ перечислимо, то его дополнение не перечислимо. В частности, не перечислимо множество машин, не заканчивающих работу при фиксированных исходных данных.

Доказательство Предположим противное, что данное свойство разрешимо. Тогда имеется машина ${\mathfrak {A}}$ , которая всегда останавливается и даёт на ленте $\cdots$ BBBMAXEEE $\cdots$ результат 1, если машина с программой M останавливается на входных данных $\cdots$ BBBXEEE $\cdots$ . Заметим, что конкретные детали кодирования здесь абсолютно несущественны, лишь бы оно было достаточно простым.

Теперь построим машину ${\mathfrak {B}}$ , которая, получив на вход $\cdots$ BBBMEEE $\cdots$ , применяет A к данным вида $\cdots$ BBBMAMEEE $\cdots$ , а затем, в случае, если результат равен 1, запускает зацикливающуюся машину. Таким образом, ${\mathfrak {B}}$ определена на $\cdots$ BBBMEEE $\cdots$ тогда и только тогда, когда ${\mathfrak {M}}$ не определена на $\cdots$ BBB $M$ EEE $\cdots$ , то есть когда машина ${\mathfrak {M}}$ некорректно работает на собственной программе.

Что же получается, если применить ${\mathfrak {B}}$ к $\cdots$ BBB $B$ EEE $\cdots$ ? Если результат определён, то, по построению, машина ${\mathfrak {A}}$ на $\cdots$ BBB $B$ A $B$ EEE $\cdots$ даёт 0, и, значит, по определению ${\mathfrak {A}}$ , ${\mathfrak {B}}$ на $\cdots$ BBB $B$ EEE $\cdots$ не определена. Если же результат не определён, то ${\mathfrak {A}}$ даёт 1, и, значит, он определён. Противоречие.

Итак, сделанное нами предположение о существовании машины, распознающей применимость, опровергнуто.

Следствие 1: Есть машина, непродолжимая до всюду определённой. Таковой является, в частности, любая универсальная машина.

Заметим, что существование неразрешимых проблем и непополнимых частичных функций не зависит от частностей теории алгоритмов. Оно следует из фундаментальнейшего факта наличия универсальной машины, и практически лишь из него.

Теперь приведём список известных классических неразрешимых проблем, который может служить ориентиром при рассмотрении других проблем (в частности, если задачу удается алгоритмическим преобразованием свести к неразрешимой, то она тоже неразрешима).

Равенство функций, вычисляемых двумя программами.
Равенство нулю результата данной программы для определённых входных данных (наборе входных данных).
Пустота (соответственно, и непустота) разрешимого множества,представленного программой, которая для каждого элемента может определить, принадлежит он этому множеству или нет.
Определение количества шагов, которое сделает программа до завершения.
Определение количества памяти, которое может понадобиться программе с динамическим выделением памяти.
Определение, зависит или не зависит в программе значение одной переменной от значения другой.
Определение, пройдёт ли когда-нибудь программа по данной ветви.
Определение, являются ли два функциональных выражения частными случаями одного и того же.
Существование положительных натуральных чисел $x_{i}$ , таких что $P(x_{1},\dots ,x_{n})=0,$ где $P$ — многочлен с целыми коэффициентами (наличия корня у диофантового уравнения).
Существование решения произвольной системы уравнений в словах.
Равенство либо неравенство ( $\neq$ , <, >) двух действительных чисел.
Доказуемость логического утверждения с кванторами или же утверждения некоторой общепринятой формальной теории (арифметики, анализа и т. д.).
Определение, переходит ли когда-нибудь данный двухголовочный автомат в состояние 0. (поскольку иначе можно было бы разрешить проблему остановки для машин Тьюринга).

Этот список можно продолжать очень долго. Есть и критерии, которые позволяют ответить на вопрос о неразрешимости сразу для некоторого класса свойств. Приведем самый известный и одновременно самый практически полезный из них.

Определение 2: Свойство $P$ программ называется функциональным, если для любых двух программ $a$ , $b$ , вычисляющих одну и ту же функцию, $P(a)\iff P(b)$ .

Теорема 2 (Теорема Райса-Успенского): Есть лишь два разрешимых функциональных свойства программ: тождественно истинное и тождественно ложное.

Множество объектов называется перечислимым, если есть алгоритм, который ничего не получает на вход, а последовательно выводит на выход объекты из этого множества, то есть для любого объекта этого множества наступит момент, когда алгоритм его выведет.

Задача: Покажите что всякое разрешимое множество перечислимо.

Вопрос: Существует ли перечислимое, но не разрешимое множество?

Доказательство Пусть $P$ — функциональное разрешимое свойство, не являющееся тривиальным. Тогда есть такие программы $a$ и $b$ , что $P(a)$ истинно, а $P(b)$ ложно. Поскольку $P$ всюду определено, оно либо истинно, либо ложно на программе для нигде не определённой функции (т.н. функции ошибка). Заменим ту из программ, значение которой совпадает с функцией ошибка, на программу для функции ошибка. Пусть это будет $a$ (второй случай рассматривается абсолютно симметрично). $P(a^{\prime })$ истинно также для любой программы $a^{\prime }$ , вычисляющей ту же функцию, что и $a$ , и ложно для любой программы $b^{\prime }$ , вычисляющей ту же функцию, что и $b$ . Рассмотрим теперь произвольную программу f и построим алгоритм (машину, функцию, комбинатор: конкретное понятие алгоритма здесь безразлично, слишком простое построение):

if f(0)=0 then b(x) else b(x).

Она будет вычислять b(x), если f(0) выдаст какое-то значение, и нигде не определённую функцию, если f(0) не определено. А теперь, применив P, решим неразрешимую проблему применимости.

Метод Британского музея

Многие из перечисленных выше не разрешимых проблем являются перечислимыми. Например, можно построить машину, которая будет перебирать всевозможные последовательности формул, и тогда она обязательно найдёт доказательство теоремы формальной теории, если только это доказательство существует. Этот исключительно неэффективный алгоритм называется методом Британского музея.

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

Метод Маркова

Если само множество, и его дополнение перечислимы, то множество разрешимо.

Доказательство. Пусть ${\mathfrak {M}}_{1}$ и ${\mathfrak {M}}_{2}$ ~— две машины, перечисляющие множество и его дополнение. Построим машину ${\mathfrak {N}}$ , разрешающую множество. С помощью универсальной машины промоделируем один шаг ${\mathfrak {M}}_{1}$ , если она не остановилась и не выдала результата, то ещё один шаг ${\mathfrak {M}}_{2}$ , и так далее, пока одна из машин не остановится. Как говорят, мы запускаем две машины квазипараллельно.

Конец доказательства

Практическая разрешимость

Чисто теоретически ‘’в принципе’’, как говорят, для разрешимой задачи можно построить программу. Но будет ли эта программа работать, зависит отнюдь не только от теоретических алгоритмов, положенных в её основу. Программа должна не просто давать приемлемый ответ, а давать его за приемлемое время и с приемлемой затратой ресурсов.

Поэтому каждый раз, когда решается практическая задача, нужно думать о её ‘’практической разрешимости’’. А это вопрос очень сложный, и успешно ответить на него могут лишь те, кто одновременно владеет и мощными теоретическими методами, и высокой практической техникой. Первого и второго по-отдельности недостаточно, более того, мнение исключительно высококвалифицированного специалиста в одной из этих областей, не компетентного в другой, в практике автора, его учеников и консультировавшихся им фирм неоднократно приводило к тем более печальным последствиям, чем выше был ранг и авторитет соответствующего специалиста.

Единого понятия практической вычислимости нет и быть не может. Приведем пример.

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

Тем не менее, если алгоритм достаточно хорошо написан, то на современных машинах проверка формулы с 25-30 переменными может занять приемлемое время. Другое дело, что, если алгоритм начал отказывать, то никакое тупое увеличение мощностей либо распараллеливание не поможет нам выиграть больше 5-7 переменных (но и это иногда спасает, правда, гораздо реже, чем хотелось бы).

В качестве инструмента решения таких задач сейчас предлагается очередная псевдонаука — квантовые компьютеры. К ней можно смело применить такой эпитет, поскольку вся теория работает здесь лишь ‘’в принципе’’ ^[3], а рекламируется как способ решать реальные задачи.

Таким образом, если данные небольшие, то часто реалистично решать экспоненциально сложные задачи.

Если данные становятся побольше (например, массивы хотя бы в несколько сотен элементов), то нужно искать алгоритмы полиномиальной сложности (число шагов машины Тьюринга ограничено некоторым многочленом). Здесь почти любой способ снизить степень полинома, оценивающего число шагов, позволяет значительно расширить класс решаемых задач. К данному классу относятся задачи так называемого линейного или динамического программирования, используемые для оптимизации планов действий, или (если попроще) перемножение матриц.

Если данные становятся еще больше (порядка миллионов данных), то даже квадратичные алгоритмы становятся неприемлемыми. Так что в типичной базе данных стремятся к тому, чтобы язык запросов содержал лишь предложения, требующие для своей обработки некоторого заранее фиксированного для данного запроса числа проходов по базе данных. Моделями таких алгоритмов служат машины Тьюринга, работающие линейное время, либо конечные автоматы. Например, реалистичным запросом является сначала найти самого недисциплинированного работника на фирме, а затем всех его родственников в базе VIP-персон, чтобы начальник, выгоняя его, не натолкнулся, не дай Бог, на мохнатую лапу. Запрос же найти двух дальше всего живущих друг от друга сотрудников является чаще всего нереалистичным, если в базе данных заранее не предусмотрено упорядочение данных по географическому принципу.

Особняком стоит сортировка данных. Она нелинейна, но чуть сложнее линейной. Поэтому базы данных стремятся всё время поддерживать в отсортированном состоянии (дешевле каждый раз ставить данные на место, чем полностью пересортировывать их время от времени). Когда же сортировку все-таки приходится делать, Вы получаете от системного администратора неприятное предупреждение, что несколько часов пользоваться базой нельзя, поскольку идёт сервисное обслуживание.

Если же мы работаем с большими базами данных (миллиарды и триллионы записей), то даже два прохода по базе чаще всего становятся слишком дорогим удовольствием, а один допустим лишь в экстренных случаях,и поэтому методы поиска используют ссылки, чтобы не заниматься сплошным перебором. Именно так действуют ведущие поисковые системы в Интернете.

Рассмотрев всё предыдущее, мы видим, что, как ни странно, сложность задач чаще всего оценивают в терминах машин Тьюринга. Да, это именно так. При переходе от машины Тьюринга к «более современным» архитектурам можно выигрывать 1-2 степени полинома на не слишком больших данных (одну частенько, две — порою), но зато резко затрудняется теоретический анализ, а более адекватным он не становится.

Но, конечно же, на машине Тьюринга никто реальные алгоритмы не пишет, и программы типа Turing's World (Корнелл, США) служат лишь для обучения. А учиться нужно не столько тому, что нужно сейчас, сколько тому, что не устареет за всю вашу жизнь.

Теперь можно сделать еще одно замечание. Тезис Чёрча противоречит общей теории относительности ^[4]. Если оставить машину Тьюринга в нашем мире (прикрепив к ней неслабую водородную бомбу, взрывающуюся, если машина кончит вычисления), а самому отправиться в путешествие через вращающуюся чёрную дыру, то за конечное время вы, согласно теории Эйнштейна, увидите всё будущее нашей Вселенной и узнаете, кончила ли машина работу (был взрыв или нет?).

Далее, аргумент типа: «Это можно запрограммировать и на С++» с логической точки зрения имеет тот же статус, что и утверждение $A\equiv A$ , то есть содержательного смысла не несёт, поскольку является тавтологией. Вопрос не в том, можно ли, а будет ли лучше, красивее, переносимее, и просто реалистичнее. Так что слушать такие аргументы нельзя, а говорить такие вещи самому — тем более. Но не стоит спорить с тем, кто так говорит: просто игнорируйте его в данном отношении, поскольку убеждённому невежде хоть кол на голове теши…

А напоследок заметим, что знание границ знания подразумевает (в идеале) и знание границ границ. Поэтому следующей статьей в серии будет «Методы Кристобаля Хунты», в которой мы разберём, «как решать нерешаемые задачи».

Дальнейшее чтение

Машина Тьюринга в Википедии.

Для тех, кто интересуется понятием алгоритма, можно посоветовать две книги: великолепный учебник лауреата Нобелевской премии(не нобелевской, а премии Тьюринга!) М. Минского^[5] и отличную, но более серьезную книгу В.А. Успенского и А.Л. Семёнова:

Минский М. Вычисления и автоматы. М.: Мир, 1971 (готовится переиздание в издательстве РХД: классика не стареет!)
Успенский В.А., Семёнов А.Л. Теория алгоритмов: основные открытия и приложения. М.: Наука, 1987.

Примечания

^ — Служит ли универсальность системы рекламой для сколько-нибудь знающего специалиста, а не для возомнившего себя крутым чайника либо хакера — это другой вопрос, к которому стоит вернуться позднее.
^ — Ада Лавлейс лишь указала на ошибки в программах Бэббиджа. Таким образом, он был первым программистом, а Лавлейс — вторым программистом и первой программисткой.
^ — Если глянуть чуть поглубже, воспользовавшись известными уже более 50 лет, но игнорируемыми физиками, понятиями теории некорректных задач, то видно, что даже в принципе теория квантовых компьютеров не работает, если учесть неизбежные в реальной жизни погрешности данных и вычислительных элементов. Но объяснять это безнадёжно, поскольку под неё дают большие деньги. А не писать об этом нельзя, поскольку провал данного направления в очередной раз будет использован болтунами и фундаменталистами как аргумент против науки и научного подхода в целом.
^ — То есть не те, на которые ориентируются наши верхи при перестройке нашего образования.
^ — Для автора не стои́т вопрос, что в данном случае предпочесть: конечно же, более подтверждённое положение!
^ — Нобелевскую премию Минский получил за то, за что его лучше бы было публично выпороть: за научную демагогию, связанную с применением теории алгоритмов к психологии; но эта книга показывает, что получил её в данном случае действительно выдающийся человек.