Talks
Speakers
Events
Topics
Sign in
Home
Talks
Speakers
Events
Topics
Leaderboard
Use
Analytics
Sign in
Suggest modification to this talk
Title
Description
We're used to using Regular Expressions every day for pattern matching and text replacement, but... What can Regexes actually do? How far can we push them? Can we implement actual logic with them? What if I told you... You can actually implement Conway's Game of Life with just a Regex? What if I told you... You can actually implement ANYTHING with just a Regex? Join me on a wild ride exploring amazing Game of Life patterns, unusual Regex techniques, Turing Completeness, programatically generating complex Regexes with Ruby, and what all this means for our understanding of what a Regex can do. RubyKaigi 2021: https://rubykaigi.org/2021-takeout/presentations/dmagliola.html
Date
Summarized using AI?
If this talk's summary was generated by AI, please check this box. A "Summarized using AI" badge will be displayed in the summary tab to indicate that the summary was generated using AI.
Show "Summarized using AI" badge on summary page
Summary
Markdown supported
In the talk "Do regex dream of Turing Completeness?" presented at RubyKaigi Takeout 2021, Daniel Magliola explores the intriguing question of whether Conway's Game of Life can be implemented using regular expressions (regex). The Game of Life, a cellular automaton, consists of a grid of cells that evolve across generations based on simple rules determining if each cell lives, dies, or reproduces. Magliola embarks on a journey to represent this logic using regex and touches on numerous key points throughout his presentation: - **Introduction to Conway's Game of Life**: The Game consists of cells that can be alive (1) or dead (0). The state of each cell changes based on the number of neighboring cells that are alive or dead. - **Challenge of Using Regex**: Regexes traditionally serve as pattern matchers, and Magliola questions how to utilize them to drive behavior and logic, as required by the Game of Life implementation. - **Implementation Approach**: Instead of a typical array representation, the board is formatted into a linear string of binary digits. Regex techniques like zero-width assertions are used to evaluate cell states by examining neighboring conditions. - **Finding Changing Cells**: Magliola discusses the difficulty of identifying cells that need to change their state using regex because of the need to count neighbors regardless of their order. He realizes that 512 combinations of conditions can be reduced to the 228 meaningful changes required to observe cell behavior in the Game of Life. - **Brute-Force Technique**: To tackle the challenge of counting neighbors, Magliola employs a brute-force method, generating regex patterns based on the changing states. - **Challenges in Regex Replacement**: As regex can select changing cells but not specify how to replace them, he introduces named captures as a solution. This innovative use of captures enables the implementation of logic to replace cells effectively within a single regex pass. - **Turing Completeness Discussion**: The talk culminates in exploring the implications of Turing completeness in relation to regex. Magliola notes that while formal regexes may not qualify as Turing complete, practical applications, as demonstrated, can emulate computation remarkably. - **Conclusion**: Although regex cannot inherently perform loops, the combination of regex techniques coupled with logic illustrates regex’s surprising capability in simulating computational processes, providing a fascinating insight into the potential of regex beyond its conventional application. Magliola encourages the audience to appreciate the versatility and depth of regex as a programming tool. In summary, this presentation serves as an exploration of the bounds of regex functionality, challenging the perception of what regex can achieve in the landscape of computational logic and programming.
Suggest modifications
Cancel
