Stories
Slash Boxes
Comments

SoylentNews is people

Lisp in Conway's Game of Life

posted by janrinok on Friday December 24 2021, @01:08AM   Printer-friendly
from the fun-for-the-holler-daze dept.

DannyB writes:

Lisp in Conway's Game of Life

Lisp in Life is a Lisp interpreter implemented in Conway's Game of Life.

[...] The Lisp interpreter, written in C, is compiled to an assembly language for a CPU architecture implemented in the Game of Life, which is a modification of the computer used in the Quest For Tetris (QFT) project. The compilation is done using an extended version of ELVM (the Esoteric Language Virtual Machine). The Game of Life backend for ELVM was implemented by myself.

Generating a short enough Lisp interpreter assembly code and a Game of Life pattern that runs in a reasonable amount of time required a lot of effort.

Having an infinite size Game of Life grid [...] reduces the chances that any pattern will wrap around to the other side of the grid.

Original Submission

 
This discussion has been archived. No new comments can be posted.
Lisp in Conway's Game of Life | Log In/Create an Account | Top | 17 comments | Search Discussion
Display Options Threshold/Breakthrough Mark All as Read Mark All as Unread
The Fine Print: The following comments are owned by whoever posted them. We are not responsible for them in any way.

  • (Score: 2) by sgleysti on Friday December 24 2021, @06:06PM

    by sgleysti (56) Subscriber Badge on Friday December 24 2021, @06:06PM (#1207624)

    Yes, good explanation. To add a little more detail, some of the "entities" in the game of life are called gliders. Per https://en.wikipedia.org/wiki/Conway%27s_Game_of_Life [wikipedia.org],

    It is possible for gliders to interact with other objects in interesting ways. For example, if two gliders are shot at a block in a specific position, the block will move closer to the source of the gliders. If three gliders are shot in just the right way, the block will move farther away. This sliding block memory can be used to simulate a counter. It is possible to construct logic gates such as AND, OR, and NOT using gliders. It is possible to build a pattern that acts like a finite-state machine connected to two counters. This has the same computational power as a universal Turing machine, so the Game of Life is theoretically as powerful as any computer with unlimited memory and no time constraints; it is Turing complete. In fact, several different programmable computer architectures have been implemented in the Game of Life, including a pattern that simulates Tetris.

    Lest you think such stunts have no practical application, the recently disclosed ForcedEntry iMessage RCE vulnerability [blogspot.com] involved carefully crafting a PDF file to cause a buffer overflow in the JBIG2 decompression algorithm whose primitive operations were then hijacked to perform logical operations on arbitrary memory locations. From this, the attackers created a virtual machine to run their payload. Stunningly brilliant. Wish the authors would have done more positive things with their prodigious talent.

    Starting Score:    1  point
    Karma-Bonus Modifier   +1  
    Total Score:   2