Можете ли вы написать функцию, которая возвращает истину, если эта функция завершается, и ложь, если нет?

Можете ли вы написать функцию JavaScript, которая принимает произвольную функцию и ввод в качестве аргументов и возвращает true, если эта функция завершает выполнение (останавливается) после вызова и false, если нет, для всех возможных комбинаций функции и ввода?

Для упражнения предположим, что наш JS Engine не привязан ни к каким ограничениям по времени или памяти и что сам движок работает безупречно.

Мы ищем что-то вроде этого:

Довольно интригующая задача, не правда ли? Давайте рассмотрим это поближе.

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

Принимая во внимание, что мы можем столь же быстро сказать, что эта другая функция всегда останавливается:

Но по мере того, как функции становятся более сложными, задача усложняется. Мы могли бы говорить о функциях с тысячами строк кода и миллионами возможных выходов в зависимости от входов.

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

Проблема остановки

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

Предположим, существует программа, которая всегда решает проблему остановки. Другими словами, представьте, что существует программа, которая категорически и правильно отвечает на вопрос: «Будет ли программа X, каким бы он ни был, при вводе Y, каким бы он ни был, завершаться или нет?» для всевозможных программ-вводов. Кроме того, предположим, что мы превратили эту программу в функцию JavaScript и импортируем эту функцию в другой модуль. Затем мы модифицируем его, поэтому, если функция возвращает true, мы делаем его циклическим, а если он возвращает false, мы выводим true.

Представьте, что вы вызываете эту новую функцию с самой собой в качестве аргумента.

В этой гипотетической программе, когда я нажимаю функцию checkIfHalts и спрашиваю ее, «будет ли checkIfHaltsModified остановиться?» если он ответит "да", наша функция doesItHalt вернет true, и программа войдет в цикл и никогда не остановится . Таким же образом, если наша гипотетическая функция ответит на наш вопрос «нет, она не остановится», doesItHalt будет false , и функция остановится и выдаст true в качестве окончательного результата - парадокс.

Reductio ad absurdum

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

Это симпатичная теоретическая штука, достаточно занимательная, но что с того? Имеет ли это какое-то практическое значение для нас, разработчиков, в нашей повседневной жизни?

На первый взгляд кажется, что нет. Имея дело с проблемой остановки, Тьюринг концептуализирует воображаемые машины с бесконечным временем и ресурсами для выполнения любых вычислений. В реальной жизни компьютер столкнется с ограничениями по времени и ресурсам. «Теоретическая программа может никогда не остановиться, но время ожидания запроса сервера точно истечет!»

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

Дайвинг глубже

Мы только что увидели, что невозможно написать программу, которая сообщает, остановится ли другая программа. Но предположим, что мы были заинтересованы не в написании программы, которая решает проблему остановки, а в программе, которая сообщает, даст ли какая-либо произвольная программа нам действительный компонент React или нет в результате ее вычислений.

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

Следуя тем же шагам, которые мы предприняли для решения проблемы остановки, представьте себе, что такая программа будет существовать в форме функции JavaScript, которую мы могли бы импортировать. Если бы это было так, оказалось, что мы могли бы использовать его для написания другой программы, которая определяет программу остановки!

Вот как:

В этом примере мы сначала создаем промежуточную функцию (g), которая выполняет произвольную функцию, переданную в качестве аргумента, не заботясь о результате, и сразу после этого возвращает компонент React. Затем мы передаем эту промежуточную функцию нашей гипотетической, которая проверяет способность функций создавать компоненты React. Если функция isAReactComponentGenerator возвращает значение true, это должно означать, что выполнение fn в конечном итоге завершится, что означает остановку. С другой стороны, если он вернет false, это должно означать, что fn никогда не закончит работу. Но если мы только что доказали, что у нас не может быть однозначного решения проблемы остановки, из этого следует, что наше предположение неверно. Другими словами, это означает, что не может быть функции, которая категорически решает, будет ли какая-либо произвольная функция возвращать компонент React или нет.

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

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

Доказав это, Райс представила новый взгляд на природу вычислений. Что Райс, Тьюринг и Черч математически показали, так это то, что не имеет значения ваша вычислительная мощность: просто невозможно придумать алгоритм, который проверяет данную программу и сообщает вам, что он будет делать для каждой возможной программы. Неважно, запускаете ли вы его на старом Intel 486 или квантовом компьютере. И здесь все становится интереснее.

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

Где встречаются программное обеспечение и реальный мир

Эти вопросы относятся не только к области компьютерных наук. У нас полно примеров похожих проблем в самых разных областях, от экономики до биологии, от психологии до медицины. Как сеть хорошо изученных нейронов может породить разум? Как из набора независимых агентов может возникнуть фондовый рынок? Как комбинация атомов могла объединиться и развиться с течением времени, чтобы дать начало существам, которые рассуждают о том, как именно эти атомы сделали это в первую очередь?

Во второй половине 20 века ученые и мыслители из разных областей начали наблюдать подобные явления, неоднократно проявляющиеся в самых разных контекстах. Повсюду одна и та же закономерность: набор простых правил начнет сложным образом сочетаться, что приведет к чему-то более значительному, но труднопонятному и невозможному для предсказания.

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

Вся эта совокупность подобных вопросов породила новую область науки под названием Сложность. Как утверждает наука, сложность - это область, которая все еще находится в зачаточном состоянии. Его основные заботы связаны с пониманием того, как возникают сложные системы. Когда-то он назывался Хаос, и именно здесь родились такие идеи, как эффект бабочки и фракталы. Интересно, что одним из основных инструментов, которые ученые использовали для понимания этих сложных систем, являются компьютеры.

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

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

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

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

Тем не менее, несмотря на эту притворную потенциальную непредсказуемость, все усилия по написанию программного обеспечения направлены на то, чтобы заставить его делать то, что мы хотим от него. Так как же нам убедиться, что он делает то, что мы хотим? Нам нравится то, что делают ученые, изучающие сложность: мы моделируем это.

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

Мы как разработчики программного обеспечения работаем именно так. Мы пишем код только для того, чтобы запустить его и проверить, выполняет ли он то, что мы хотим, потому что в противном случае мы не сможем сказать, что будет делать система, над которой мы работаем. Другими словами, самый эффективный способ узнать, что будет делать любая нетривиальная программная система, - это запустить ее. И это не ограничение человеческого разума, а фундаментальный закон природы. Закон, на который Тьюринг, Черч и Райс указывали нам языком логики и математики несколько десятилетий назад.

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

Это потому, что нет другого более эффективного способа справиться с врожденной сложной природой кода, который вы пишете для тестов.

Последние мысли

Из математического доказательства, опубликованного Аланом Тьюрингом в 1931 году, за два десятилетия до появления нашего первого языка программирования, мы уже могли смотреть на сложный мир, который откроют логические машины. Отсюда мы можем проследить путь познания, открываемого в науке, который ведет к нашей повседневной работе, и объяснить, почему мы делаем некоторые вещи, которые мы делаем, например, написание тестов.

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

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