Доказательство Тьюринг-полноты однострочников на Python13.11.2021 16:16

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

Оказалось — да!

Немного теории

Исполнитель называется Тьюринг-полным, если на нём можно реализовать любую вычислимую функцию, и наоборот. То есть, чтобы доказать что в одну строку на Python можно написать какой угодно код, необходимо доказать Тьюринг-полноту однострочных программ на python. Как это сделать ?

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

Чёткие правила данного автомата изложены в Википедии по ссылке здесь.

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

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

Реализация

Сразу уточню, что символ »;» я считал началом новой строки, чем он по сути и является, иначе задача превращается в тривиальную.

Итак, опредилившись с тем что же именно я собираюсь написать, я, недолго думая, запустил VSCode и… И завис. Потому что неясно было что писать. Ясно было, что нужен цикл while, ввод начального состояния, которое нужно как-то обработать, действия над ним в цикле, Кроме того, цикл надо ещё как-то остановливать, если состояние системы стабилизировалось и больше не меняется.

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

# А не работает так!
while (a=int(input()) or a!=0):print(a)

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

#Объявление
globals.update({"a":0})
#Получение значения
globals.get("a")
# Простейший цикл while
while (globals.update({"a":int(input())}) or globals.get("a")!=0):print(globals.get("a"))

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

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

https://github.com/Thane784/rule_110

Куда же тыкать ?

Итоговый код и как он работает

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

Для этого заведем две глобальные переменные «s» (string) и «l» (last). Да, я знаю, что s и l — не очень хорошие названия для переменных, но для одноразового кода, который никто в дальнейшем поддерживать не будет, думаю нормально.

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

# Записываем нач. состояние в переменную,
# выводим его же в консоль, 
# причём только если предыдущего состояния нет,
# то есть на первой иттерации цикла,
# используем оператор or для исполнения кода.
# По факту в сравнение пойдет лишь globals().get("s")),
# которое мы и сравниваем с предыдущим состоянием globals().get("l"))
while (( ( globals().update({"s": input()}) or print(globals().get("s"))) if globals().get("l") == None else None) or globals().get("s")) != globals().get("l"): print('')t('')

Далее, уже в теле цикла мы объявляем фиктивную переменную a которой присваиваем значение длинного длинного сравнения через оператор or. На самом деле, оператор сравнения здесь нужен чтобы выполнить большое количество исполняемого кода, в котром каждая вызываемая функция вернёт None. Возможно, можно было реализовать подобное более красиво, но это самое быстрое рабочее решение, которое пришло мне в голову.

#Скелет
while last_code: a = (func1() or func2() or func3() or 1)

В полном же варианте нарощенном на данный скелет мы обновляем l (предыдущее состояние), проходим один цикл клеточного автомата, перезаписывая переменную s, и выводим новое состояние.

Для хранения состояния используем строку, постепенно обрабатывая её, собираем массив, который содержит новое состояние. Этот массив затем приводим к строке при помощи функции ''.join () и перезаписываем глобальную переменную s. Скорее всего, можно было бы обойтись без массива, но оптимизация здесь не слишком важна. Также, при определённых условиях расширяем наблюдаемую область (если в результате работы алгоритма «оживились» клетки, ранее нами не отслеживаемые (поле, естесственно бесконечно), откуда кстати и проблемы с выводом — довольно скоро поле становится ОЧЕНЬ большим). Большую часть кода занимает вычисление следующего состояния на основе предыдущего, это просто множество условий if elif else записанных в одну строчку.

Вот так выглядит финальный код.

while (( ( globals().update({"s": input()}) or print(globals().get("s"))) if globals().get("l") == None else None) or globals().get("s")) != globals().get("l"): a = ( globals().update({"l": (globals().get("s"))}) or globals().update({"s": (''.join(['1' if globals().get("s")[0] == '1' else '']+[('0' if (n != 0 and n!=(len(globals().get("s"))-1) and (globals().get("s")[n-1:n+2] == '000' or globals().get("s")[n-1:n+2] == '100' or globals().get("s")[n-1:n+2] == '111') ) else '0' if (n == (len(globals().get("s"))-1) and ( ((globals().get("s")[-2] if len(globals().get("s"))>1 else '0')+globals().get("s")[-1]) == '00' or ((globals().get("s")[-2] if len(globals().get("s"))>1 else '0')+globals().get("s")[-1]) == '10') ) else '0'  if (n == 0 and globals().get("s")[0]+(globals().get("s")[1] if len(globals().get("s"))>1 else '0') == '00'  ) else '1') for n in range(0,len(globals().get("s")))]) )})  or (print(globals().get("s")) if globals().get("s") != globals().get("l") else None) or 1) or 1)

Что же в итоге?

Итак! Мы написали в одну строчку Тьюринг-полную систему, чем доказали, что однострочники на python обладают Тьюринг-полнотой. Что же это значит ? Это значит, что в одну строчку python кода можно написать всё что угодно ! Даже Windows 11 или ядро Linux.

Правда, скорее всего, код получится слегка нечитаемым да и дебаггинг будет затруднён…)

P. s.

© Habrahabr.ru