The OpenNET Project / Index page

[ новости /+++ | форум | теги | ]



"Построение полной по Тьюрингу вычислительной среды при помощи утилит GNU find и mkdir"
Вариант для распечатки  
Пред. тема | След. тема 
Форум Разговоры, обсуждение новостей
Изначальное сообщение [ Отслеживать ]

"Построение полной по Тьюрингу вычислительной среды при помощи утилит GNU find и mkdir"  +/
Сообщение от opennews (??), 31-Июл-24, 10:23 
Японский разработчик Keigo Oka продемонстрировал, что на основе утилит GNU find и mkdir можно сформировать вычислительную среду, являющуюся полной по Тьюрингу, т.е. позволяющую реализовать на нём любую вычислимую функцию и воссоздать себя. Ранее возможность создания подобной среды была продемонстрирована для утилит sed и awk. Для подтверждения полноты по Тьюрингу предоставлены реализации на связке из find и mkdir игры Fizz buzz и клеточного автомата, действующего по "правилу 110"...

Подробнее: https://www.opennet.dev/opennews/art.shtml?num=61635

Ответить | Правка | Cообщить модератору

Оглавление

Сообщения [Сортировка по времени | RSS]


1. "Построение полной по Тьюрингу вычислительной среды при помощ..."  +22 +/
Сообщение от Wed (??), 31-Июл-24, 10:23 
Ждем, когда с помощью утилит GNU find и mkdir будет написан DOOM.


Ответить | Правка | Наверх | Cообщить модератору

12. "Построение полной по Тьюрингу вычислительной среды при помощ..."  +18 +/
Сообщение от Аноним (12), 31-Июл-24, 11:23 
Дописан Hurd.
Ответить | Правка | Наверх | Cообщить модератору

13. Скрыто модератором  +8 +/
Сообщение от Аноним (13), 31-Июл-24, 11:28 
Ответить | Правка | Наверх | Cообщить модератору

47. "Построение полной по Тьюрингу вычислительной среды при помощ..."  +1 +/
Сообщение от Аноним (47), 02-Авг-24, 04:20 
Скорее кастрюли вступят в Евросоюз.
Ответить | Правка | К родителю #12 | Наверх | Cообщить модератору

50. "Построение полной по Тьюрингу вычислительной среды при помощ..."  +/
Сообщение от Аноним (50), 06-Авг-24, 17:37 
Это всего лишь аксиоматическая система!
Этому еще в школе учат!
Сколько параллельных прямых может пересекаться в сферическом кубе в вакууме Пуанкаре в мерности полного Перельмана...
Ответить | Правка | К родителю #1 | Наверх | Cообщить модератору

2. "Построение полной по Тьюрингу вычислительной среды при помощ..."  +4 +/
Сообщение от Аноним (2), 31-Июл-24, 10:24 
Вот так, с помощью нехитрых приспособлений буханку белого (или черного) хлеба можно превратить в троллейбус... Но зачем?
Ответить | Правка | Наверх | Cообщить модератору

4. "Построение полной по Тьюрингу вычислительной среды при помощ..."  +15 +/
Сообщение от Аноним (4), 31-Июл-24, 10:32 
Что значит зачем?
Ответить | Правка | Наверх | Cообщить модератору

8. "Построение полной по Тьюрингу вычислительной среды при помощ..."  +7 +/
Сообщение от User (??), 31-Июл-24, 10:55 
"Во первых, это красиво..."(С)
Ответить | Правка | К родителю #2 | Наверх | Cообщить модератору

10. "Построение полной по Тьюрингу вычислительной среды при помощ..."  +2 +/
Сообщение от Аноним (10), 31-Июл-24, 11:15 
>Но зачем?

Потомушта японский разработчик - это вовсе не кот, а заняться нечем.

Ответить | Правка | К родителю #2 | Наверх | Cообщить модератору

30. "Построение полной по Тьюрингу вычислительной среды при помощ..."  –1 +/
Сообщение от Аноним (30), 31-Июл-24, 19:08 
> Вот так, с помощью нехитрых приспособлений буханку белого (или черного) хлеба можно превратить в троллейбус... Но зачем?

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

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

Ответить | Правка | К родителю #2 | Наверх | Cообщить модератору

34. "Построение полной по Тьюрингу вычислительной среды при помощ..."  +/
Сообщение от Аноним (-), 31-Июл-24, 21:11 
> если у тебя есть магазин, и у твоего конкурента тоже магазин, и там продаётся хлеб,
> то ты сможешь передавить его сотрудников троллейбусом и обанкротить его бизнес.

Таким троллейбусом разве что тараканов передавить можно. Будет ли кто скучать о таких сотрудниках - вопрос интересный.

Ответить | Правка | Наверх | Cообщить модератору

3. "Построение полной по Тьюрингу вычислительной среды при помощ..."  +1 +/
Сообщение от Аноним (3), 31-Июл-24, 10:32 
Ну find может находить что-то или не находить, значит уже можно условия делать
Ответить | Правка | Наверх | Cообщить модератору

6. Скрыто модератором  +5 +/
Сообщение от Аноним (6), 31-Июл-24, 10:35 
Ответить | Правка | Наверх | Cообщить модератору

9. "Построение полной по Тьюрингу вычислительной среды при помощ..."  +3 +/
Сообщение от Фрол (?), 31-Июл-24, 10:57 
Э-э-э!

Я с помощью find -exec ваще все что угодно доказать могу.

Ответить | Правка | Наверх | Cообщить модератору

17. "Построение полной по Тьюрингу вычислительной среды при помощ..."  +3 +/
Сообщение от Аноним (2), 31-Июл-24, 12:01 
Нихрена себе! Реально тюринг-полный!
Ответить | Правка | Наверх | Cообщить модератору

25. "Построение полной по Тьюрингу вычислительной среды при помощ..."  +8 +/
Сообщение от Аноним (4), 31-Июл-24, 15:14 
Он не полный у него функциональность широкая.
Ответить | Правка | Наверх | Cообщить модератору

11. "Построение полной по Тьюрингу вычислительной среды при помощ..."  –4 +/
Сообщение от Golangdev (?), 31-Июл-24, 11:19 
> Японский разработчик Keigo Oka продемонстрировал, что на основе утилит GNU find и mkdir можно сформировать вычислительную среду, являющуюся полной по Тьюрингу

Когда делать нечего, как говорится...

Полнота по Тьюрингу - ничто, интеграция с системой, экосистемы (сорян за тавтологию) например, каку у Go, Rust - всё.

Ответить | Правка | Наверх | Cообщить модератору

16. "Построение полной по Тьюрингу вычислительной среды при помощ..."  +/
Сообщение от Аноним (4), 31-Июл-24, 11:42 
В том то и дело что ты перечислил каку.
Ответить | Правка | Наверх | Cообщить модератору

23. "Построение полной по Тьюрингу вычислительной среды при помощ..."  –1 +/
Сообщение от Аноним (23), 31-Июл-24, 14:59 
Так он про сишку не писал.
Ответить | Правка | Наверх | Cообщить модератору

33. "Построение полной по Тьюрингу вычислительной среды при помощ..."  +2 +/
Сообщение от Golangdev (?), 31-Июл-24, 20:30 
Удачи в программировании на таких "Тьюринг-полных языках". Она тебе понадобится :)

Ничего сложнее калькулятора не нём не напишешь, да и то с натяжкой.

Ответить | Правка | К родителю #16 | Наверх | Cообщить модератору

45. "Построение полной по Тьюрингу вычислительной среды при помощ..."  +/
Сообщение от Kuromi (ok), 02-Авг-24, 02:54 
Да нет, просто есть разница между теоретическими игрушками и практическим применением. Некоторые энтузиасты в гараже примитивные процессоры на лампах и память на ферритах паяют, это круто, но совершенно лишено практической ценности.

С другой стороны, будь мы 100% за пользу и 0% фантазии мы были бы пчелами.

Ответить | Правка | К родителю #16 | Наверх | Cообщить модератору

44. "Построение полной по Тьюрингу вычислительной среды при помощ..."  +/
Сообщение от MaleDog (?), 01-Авг-24, 21:47 
Не могу сказать тебе за Rust остальные, но в Go поиск обычно делается рекурсивным обходом каталогов а не вызовом внешнего find. Хотя конечно можно и так. С другой стороны, часто мы видим уязвимость вида "ну мы тут собрали все параметры. передадим их без проверки в командную строку" от этого никакой язык не застрахован.
Ответить | Правка | К родителю #11 | Наверх | Cообщить модератору

18. "Построение полной по Тьюрингу вычислительной среды при помощ..."  +2 +/
Сообщение от Аноним (18), 31-Июл-24, 12:36 
> find x -maxdepth 3 -execdir mkdir x/x \;

Вирусописатели возбудилась от этой новости. Очередной экзотический способ что-то сделать при постпроникновении

Ответить | Правка | Наверх | Cообщить модератору

31. "Построение полной по Тьюрингу вычислительной среды при помощ..."  +/
Сообщение от I use Arch btw (?), 31-Июл-24, 19:49 
Чем это лучше rm -rf? НЕНУЖНО!
Ответить | Правка | Наверх | Cообщить модератору

36. "Построение полной по Тьюрингу вычислительной среды при помощ..."  –1 +/
Сообщение от Аноним (36), 31-Июл-24, 23:56 
Ну rm червя тебе не напишет
Ответить | Правка | Наверх | Cообщить модератору

22. "Построение полной по Тьюрингу вычислительной среды при помощ..."  +/
Сообщение от Middle Go Developer (?), 31-Июл-24, 14:04 
Типичная работа с Linux, мучения ради мучений
Ответить | Правка | Наверх | Cообщить модератору

24. "Построение полной по Тьюрингу вычислительной среды при помощ..."  +1 +/
Сообщение от pavel_simple. (?), 31-Июл-24, 15:12 
отличный тест файловой системы должен получиться
Ответить | Правка | Наверх | Cообщить модератору

46. "Построение полной по Тьюрингу вычислительной среды при помощ..."  +/
Сообщение от Kuromi (ok), 02-Авг-24, 02:55 
Тест на ушатывание, да. Хотя можно в tmpfs, там вроде и ломать нечего.
Ответить | Правка | Наверх | Cообщить модератору

27. "Построение полной по Тьюрингу вычислительной среды при помощ..."  +2 +/
Сообщение от Аноним (27), 31-Июл-24, 16:31 
Расходимся.
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.
Ответить | Правка | Наверх | Cообщить модератору

28. "Построение полной по Тьюрингу вычислительной среды при помощ..."  +/
Сообщение от Аноним (28), 31-Июл-24, 16:37 
Так данный синдром и назовут: "синдром Тюрика"
Ответить | Правка | Наверх | Cообщить модератору

29. "Построение полной по Тьюрингу вычислительной среды при помощ..."  +/
Сообщение от Аноним (-), 31-Июл-24, 16:58 
Пожалуйста, объясните мне, почему все так тащатся от концепции "полный по Тьюрингу"? Чем оно кардинально лучше от неполных вычислительный сред?
Ответить | Правка | Наверх | Cообщить модератору

32. "Построение полной по Тьюрингу вычислительной среды при помощ..."  +/
Сообщение от I use Arch btw (?), 31-Июл-24, 19:53 
Потому что:

> возможность воссоздать себя

"Итерация свойственна человеку, рекурсия божественна."

Ответить | Правка | Наверх | Cообщить модератору

35. "Построение полной по Тьюрингу вычислительной среды при помощ..."  +/
Сообщение от Аноним (-), 31-Июл-24, 21:37 
> Пожалуйста, объясните мне, почему все так тащатся от концепции "полный по Тьюрингу"?
> Чем оно кардинально лучше от неполных вычислительный сред?

Тем что Тюринг-полные среды теоретически позволяют ВСЕ. Включая воссоздание других тюринг полных сред - они все теоретически эквивалентны. Практически, конечно, есть некоторые нюансы.

Ответить | Правка | К родителю #29 | Наверх | Cообщить модератору

37. "Построение полной по Тьюрингу вычислительной среды при помощ..."  +/
Сообщение от Аноним (-), 01-Авг-24, 00:44 
> Тюринг-полные среды теоретически позволяют ВСЕ.

Не ВСЁ, они не могут полететь к Проксиме Центавра, или решить NP-hard проблему за константное время. Правильнее сказать, что Тьюринг-полные среды позволяют всё, что позволяют Тьюринг-полные среды. И в этой более строгой форме высказывания, становится ясно, что твоё заявление -- тавтология, то есть пустое сотрясение воздуха.

Ответить | Правка | Наверх | Cообщить модератору

38. "Построение полной по Тьюрингу вычислительной среды при помощ..."  +/
Сообщение от Аноним (-), 01-Авг-24, 12:56 
>> Тюринг-полные среды теоретически позволяют ВСЕ.
> Не ВСЁ, они не могут полететь к Проксиме Центавра,

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

> или решить NP-hard проблему за константное время.

И даже это ну такое утверждение. Как минимум за полиномиальное - может да, а может нет.

> высказывания, становится ясно, что твоё заявление -- тавтология, то есть пустое
> сотрясение воздуха.

Рекурсивное определение не сильно далеко от него ушло. Более того - оно не доносит и ряд иных моментов. Скажем, тьюринг полные системы могут и многое из того что могут тьюринг-неполные системы, но в вашем определении это нигде не адресовано. Как простой пример: микроконтроллер может заменить (тюринг неполную) кучу релюшек, 1 в 1 или - с превышением.

Ответить | Правка | Наверх | Cообщить модератору

39. "Построение полной по Тьюрингу вычислительной среды при помощ..."  +/
Сообщение от Александр (??), 01-Авг-24, 16:10 
Если используется релюха на размыкание, можно реализовать NOR или OR-NOT базис, который является Тьюринг-полным. Т.е. релюхи Тьюринг полные
Ответить | Правка | Наверх | Cообщить модератору

41. "Построение полной по Тьюрингу вычислительной среды при помощ..."  +/
Сообщение от Аноним (-), 01-Авг-24, 16:21 
> Они могут сэмулировать...

Но не полететь. Машина Тьюринга не Бог, она не всесильна.

> И даже это ну такое утверждение. Как минимум за полиномиальное - может да, а может нет.

Но не за константное. Ты не сможешь на машине Тьюринга отсортировать массив длины N за константное время, не зависящее от N. И сортировка вовсе не NP-hard.

> в вашем определении это нигде не адресовано

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

> микроконтроллер может заменить (тюринг неполную) кучу релюшек, 1 в 1 или - с превышением.

Это ближе к ответу на вопрос, но недостаточно.

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

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

Ответить | Правка | К родителю #38 | Наверх | Cообщить модератору

40. "Построение полной по Тьюрингу вычислительной среды при помощ..."  +/
Сообщение от Аноним (40), 01-Авг-24, 16:18 
Уже опровергли. Исправьте новость
Ответить | Правка | Наверх | Cообщить модератору

43. "Построение полной по Тьюрингу вычислительной среды при помощ..."  +/
Сообщение от Аноним (43), 01-Авг-24, 20:28 
Там нашли косяк, но автор его уже исправил https://news.ycombinator.com/item?id=41127041
Исправленный пруф пока никто не опроверг
Ответить | Правка | Наверх | Cообщить модератору

48. "Построение полной по Тьюрингу вычислительной среды при помощ..."  +/
Сообщение от Аноним (48), 02-Авг-24, 06:51 
Не совсем понятно, что обсуждаем. Результаты научного изыскания точно не сгенерированы "ради смеха"?
Ответить | Правка | Наверх | Cообщить модератору

Архив | Удалить

Рекомендовать для помещения в FAQ | Индекс форумов | Темы | Пред. тема | След. тема




Партнёры:
PostgresPro
Inferno Solutions
Hosting by Hoster.ru
Хостинг:

Закладки на сайте
Проследить за страницей
Created 1996-2024 by Maxim Chirkov
Добавить, Поддержать, Вебмастеру