Max Home IndustryОдно дело знать, что что-то маловероятное является полным по Тьюрингу; совсем другое — использовать его для создания компьютера, а затем реализовать что-то реальное. Именно это и произошло с «Game Of Life» Конвея, когда был сконструирован компьютер для игры в тетрис. Это замечательное достижение, которое должно поставить ваш мозг в штопор.
Более года назад на StackExchange была поставлена задача создать реализацию тетриса Game Of Life (GoL).
Уже давно известно, что GoL является полным по Тьюрингу, то есть его можно использовать для реализации любых вычислений, но сложность реализации Тетриса огромна. Энтузиасты GoL уже довольно давно раздвигают границы этой идеи, и размер многих их конструкций затрудняет постороннему взгляду, как создаются такие вещи. Например, существует конструкция, известная как метапиксель, которая может имитировать любое другое расположение, но имеет размер 2048×2048 пикселей. Уловка, похоже, заключается в том, что через некоторое время вы начинаете думать о все более и более крупных функциональных единицах и собирать их вместе, чтобы создавать новые и еще более крупные функциональные единицы.
Задача висела некоторое время, а затем группа энтузиастов, исследователей GoL, трудно понять, как их назвать, начала приносить какие-то результаты. Проект Github и чат-комната позволили команде с различным составом работать над мегапроектом — что-то вроде самогона GoL.
Из метапикселя команда сначала построила логические ворота. В принципе, если у вас есть набор вентилей, можно использовать процессор. В конце концов, наши компьютеры, не относящиеся к GoL, построены только из простых логических вентилей. В принципе, все, что вам нужно, это гейт Nand, но на практике немного проще иметь разнообразие.
От логических ворот команда начала восхождение на пирамиду сложности. От ворот до более сложных процессоров, триггеров, хранилища, арифметического устройства, ПЗУ и так далее.
Блок ОЗУ с метапикселями 22×22
Затем они разработали асинхронный процессор и язык ассемблера под названием QFTASM Quest for Tetris Assembly. Следующим шагом стал язык высокого уровня под названием Cogol, и бэкэнд для GCC все еще находится в стадии разработки, который позволит скомпилировать завершенные программы C / C ++ в Cogol.
Настоящая игра Тетрис была написана на Cogol и скомпилирована в QFTASM, и это довольно полная реализация с набором частей, командой перетаскивания, подсчетом очков и предварительным просмотром следующей части. Полученный машинный код был автоматически преобразован в ПЗУ.
«Итак, наш компьютер (с ПЗУ Тетриса) имеет ограничивающую рамку размером 1436 x 5082. Из 7 297 752 ячеек в этом поле 6 075 811 пустое пространство, в результате чего фактическая численность населения составляет 12 21 941 человек. Каждую из этих ячеек необходимо преобразовать в метапиксель OTCA, который имеет ограничивающую рамку 2048×2048 и население либо 64 691 (для метапикселя ON), либо 23 920 (для метапикселя OFF). Это означает, что конечный продукт будет иметь ограничивающую рамку 2 940 928 x 10 407 936 (плюс несколько тысячи дополнительных для границ метапикселей) с населением от 29 228 828 720 до 79 048 585 231. С 1 битом на живую ячейку это от 27 до 74 ГиБ, необходимых для представления всего компьютера и ПЗУ ».
Если вы хотите увидеть игру в действии, самый быстрый способ — обратиться к интерпретатору QFTASM и посмотреть, как он там работает. Кусочки можно рассматривать как узоры из битов в ячейках памяти с 10 по 31. Вы должны уметь распознавать знакомые формы. Управление игрой сложнее и требует прямого ввода в память — здесь нет ввода с клавиатуры.
Я уверен, что многие люди смотрели на работающую программу QFTASM и были впечатлены, но, честно говоря, это всего лишь интерпретатор языка ассемблера для воображаемой машины. Это не тетрис на GoL. Чтобы увидеть настоящую вещь, вам нужно загрузить Golly, высокоскоростную программу GoL и исходный файл шаблона, загрузить его в Golly и увидеть, как все это работает — теперь это потрясающе. Но на самом деле играть в нее намного сложнее, потому что в памяти нет удобного побитового дисплея, как в симуляторе.
Несомненно, это приведет к появлению сообщений о том, что мы живем в симуляции симуляции симуляции, но настоящая правда глубже. Полнота по Тьюрингу означает полноту по Тьюрингу, и с такими простыми вещами вы можете делать все, что можно.
АЛУ