Японский разработчик Keigo Oka продемонстрировал, что на основе утилит GNU find и mkdir можно сформировать вычислительную среду, являющуюся полной по Тьюрингу, т.е. позволяющую реализовать на нём любую вычислимую функцию и воссоздать себя. Ранее возможность создания подобной среды была продемонстрирована для утилит sed и awk. Для подтверждения полноты по Тьюрингу предоставлены реализации на связке из find и mkdir игры Fizz buzz и клеточного автомата, действующего по "правилу 110"...Подробнее: https://www.opennet.dev/opennews/art.shtml?num=61635
Ждем, когда с помощью утилит GNU find и mkdir будет написан DOOM.
Дописан Hurd.
> Дописан Hurd.Не, ну давай обсуждать реалистичные события.
Ну типа полета к альфацентавре, телепортацию или лекарство для бессмертия.
Скорее кастрюли вступят в Евросоюз.
Это всего лишь аксиоматическая система!
Этому еще в школе учат!
Сколько параллельных прямых может пересекаться в сферическом кубе в вакууме Пуанкаре в мерности полного Перельмана...
Вот так, с помощью нехитрых приспособлений буханку белого (или черного) хлеба можно превратить в троллейбус... Но зачем?
Что значит зачем?
"Во первых, это красиво..."(С)
>Но зачем?Потомушта японский разработчик - это вовсе не кот, а заняться нечем.
> Вот так, с помощью нехитрых приспособлений буханку белого (или черного) хлеба можно превратить в троллейбус... Но зачем?как зачем?
если у тебя есть магазин, и у твоего конкурента тоже магазин, и там продаётся хлеб, то ты сможешь передавить его сотрудников троллейбусом и обанкротить его бизнес.а касательно утилит, выходит, что любой код можно выполнить на системе, где можно запускать find и mkdir и есть директория с правами на запись.
> если у тебя есть магазин, и у твоего конкурента тоже магазин, и там продаётся хлеб,
> то ты сможешь передавить его сотрудников троллейбусом и обанкротить его бизнес.Таким троллейбусом разве что тараканов передавить можно. Будет ли кто скучать о таких сотрудниках - вопрос интересный.
Ну find может находить что-то или не находить, значит уже можно условия делать
Всем известно, что японцы знают толк в извращениях. Но этот решил переплюнуть всех.
Э-э-э!Я с помощью find -exec ваще все что угодно доказать могу.
Нихрена себе! Реально тюринг-полный!
Он не полный у него функциональность широкая.
> Японский разработчик Keigo Oka продемонстрировал, что на основе утилит GNU find и mkdir можно сформировать вычислительную среду, являющуюся полной по ТьюрингуКогда делать нечего, как говорится...
Полнота по Тьюрингу - ничто, интеграция с системой, экосистемы (сорян за тавтологию) например, каку у Go, Rust - всё.
В том то и дело что ты перечислил каку.
Так он про сишку не писал.
Удачи в программировании на таких "Тьюринг-полных языках". Она тебе понадобится :)Ничего сложнее калькулятора не нём не напишешь, да и то с натяжкой.
Да нет, просто есть разница между теоретическими игрушками и практическим применением. Некоторые энтузиасты в гараже примитивные процессоры на лампах и память на ферритах паяют, это круто, но совершенно лишено практической ценности.С другой стороны, будь мы 100% за пользу и 0% фантазии мы были бы пчелами.
Не могу сказать тебе за Rust остальные, но в Go поиск обычно делается рекурсивным обходом каталогов а не вызовом внешнего find. Хотя конечно можно и так. С другой стороны, часто мы видим уязвимость вида "ну мы тут собрали все параметры. передадим их без проверки в командную строку" от этого никакой язык не застрахован.
> find x -maxdepth 3 -execdir mkdir x/x \;Вирусописатели возбудилась от этой новости. Очередной экзотический способ что-то сделать при постпроникновении
Чем это лучше rm -rf? НЕНУЖНО!
Ну rm червя тебе не напишет
Типичная работа с Linux, мучения ради мучений
отличный тест файловой системы должен получиться
Тест на ушатывание, да. Хотя можно в tmpfs, там вроде и ломать нечего.
Расходимся.
The proof is flawed and I retract the claim that I proved that find + mkdir is Turing complete. See https://news.ycombinator.com/item?id=41117141. I will update the article if I could fix the proof.
Так данный синдром и назовут: "синдром Тюрика"
Пожалуйста, объясните мне, почему все так тащатся от концепции "полный по Тьюрингу"? Чем оно кардинально лучше от неполных вычислительный сред?
Потому что:> возможность воссоздать себя
"Итерация свойственна человеку, рекурсия божественна."
> Пожалуйста, объясните мне, почему все так тащатся от концепции "полный по Тьюрингу"?
> Чем оно кардинально лучше от неполных вычислительный сред?Тем что Тюринг-полные среды теоретически позволяют ВСЕ. Включая воссоздание других тюринг полных сред - они все теоретически эквивалентны. Практически, конечно, есть некоторые нюансы.
> Тюринг-полные среды теоретически позволяют ВСЕ.Не ВСЁ, они не могут полететь к Проксиме Центавра, или решить NP-hard проблему за константное время. Правильнее сказать, что Тьюринг-полные среды позволяют всё, что позволяют Тьюринг-полные среды. И в этой более строгой форме высказывания, становится ясно, что твоё заявление -- тавтология, то есть пустое сотрясение воздуха.
>> Тюринг-полные среды теоретически позволяют ВСЕ.
> Не ВСЁ, они не могут полететь к Проксиме Центавра,Они могут сэмулировать этот полет. И даже создать виртуальную реальность, будучи подключенными к которой, при достаточном уровне технологий вы будете уверенны что летите к Проксиме Центавра. Более того, есть теории что вселенная также может быть подобной структурой и это лишь эмуляция. Доказать или опровергнуть такой тезис, разумеется, проблематично.
> или решить NP-hard проблему за константное время.
И даже это ну такое утверждение. Как минимум за полиномиальное - может да, а может нет.
> высказывания, становится ясно, что твоё заявление -- тавтология, то есть пустое
> сотрясение воздуха.Рекурсивное определение не сильно далеко от него ушло. Более того - оно не доносит и ряд иных моментов. Скажем, тьюринг полные системы могут и многое из того что могут тьюринг-неполные системы, но в вашем определении это нигде не адресовано. Как простой пример: микроконтроллер может заменить (тюринг неполную) кучу релюшек, 1 в 1 или - с превышением.
Если используется релюха на размыкание, можно реализовать NOR или OR-NOT базис, который является Тьюринг-полным. Т.е. релюхи Тьюринг полные
> Они могут сэмулировать...Но не полететь. Машина Тьюринга не Бог, она не всесильна.
> И даже это ну такое утверждение. Как минимум за полиномиальное - может да, а может нет.
Но не за константное. Ты не сможешь на машине Тьюринга отсортировать массив длины N за константное время, не зависящее от N. И сортировка вовсе не NP-hard.
> в вашем определении это нигде не адресовано
Я не давал определения тьюринг-полноте. Если тебе оно нужно, то оно грубо говоря сводится к тому, что тьюринг-полная система может всё, что может машина тьюринга. Но оно тоже не даёт ответа на вопрос ТСа: что это все носятся к тьюринг-полнотой, как курица с яйцом.
> микроконтроллер может заменить (тюринг неполную) кучу релюшек, 1 в 1 или - с превышением.
Это ближе к ответу на вопрос, но недостаточно.
Любая из современных вычислительных систем, максимум, может сравняться с машиной Тьюринга по своим возможностям, но не превзойти. Ассимптотические сложности алгоритмов рассчитанные для машины Тьюринга будут на любой реальной современной машине либо такими же, либо хуже. Масштабы этого "хуже" могут достигать невозможности решить задачу на слишком ущербной машине, вне зависимости от затраченного времени. В исключения попадает квантовый компьютер, который может выполнять за O(1) операции, которые для машины Тьюринга далеко не O(1). Но тут есть простор для дебатов насчёт того, насколько это исключение реально современно, а не мечты о светлом будущем.
Мало того, есть математические методы работы с утверждениями о тьюринг-полноте и связанных вещах. Методы достаточно примитивные, чтобы им можно было обучить инженеров. И это как раз открывает простор для того, чтобы, например, не ломать пять лет голову, как решить задачу на недостаточно гибком железе, а доказать невозможность такого решения, и использовать тот самый микроконтроллер.
Уже опровергли. Исправьте новость
Там нашли косяк, но автор его уже исправил https://news.ycombinator.com/item?id=41127041
Исправленный пруф пока никто не опроверг
Не совсем понятно, что обсуждаем. Результаты научного изыскания точно не сгенерированы "ради смеха"?