Skip to content
Hallway
0:00 / 0:00

#rule110#turingcompleteness#cellularautomata

Eli Fox-Epstein's Rule 110 HTML & CSS3 Machine

Brian Krent

12 subscribers • 1 video on Hallway

YouTube
  • Recommended by 1 person: 1 in engineering communities.
  • A classic. People kept recommending it from 2020 to 2024.
  • Presented by Eli Fox-Epstein
  • Linked in the descriptionelitheeli/stupid-machines
  • May be out of date. Uploaded 14 years ago, in an area where tools change fast.

Intermediate. Assumes working knowledge.

26K views14 years ago1 recommendation

Computer scienceWeb developmentComputation and complexityCSS and layout

A demonstration of a Rule 110 cellular automaton implemented entirely in HTML and CSS without JavaScript to show Turing completeness.

A demonstration of a Rule 110 machine implemented in HTML & CSS3 (and with no JavaScript) by Eli Fox-Epstein. ❝For those confused, here's a proper explanation. No real-world thing can actually be Turing complete (able to express basically any computation that we might want to perform of any size). That's because there are finitely many atoms in the universe, so we can only construct machines of finite size. It's well known that Rule 110 (Google it) is Turing Compete. What I've done is made an implementation of Rule 110 in HTML and CSS. Since CSS can't actually really manipulate state, some user interaction is required to "drive" it. ... The tab-space combo is just as legitimate as requiring that you plug a computer into a wall to power it in order to run a Java program. elilies.com/rule110-full.html‌❞ (Eli Fox-Epstein, Hacker News news.ycombinator.com/item?id=2301146‌, 2011 March 9) HTML+CSS Machine Implementation: • eli.fox-epste.in/rule110-full.html • github.com/elitheeli/stupid-machines/tree/master/rule110 CSS3 Selectors Reference: • w3.org/TR/selectors/ Rule 110 Information: • en.wikipedia.org/wiki/Rule_110 • mathworld.wolfram.com/Rule110.html

Why it's here

1 person recommends this

What people say. Engineers point to this to discuss the boundaries of Turing completeness and non-Turing complete languages.

u/RobertJacobsonin r/ProgrammingLanguages • Recommends

On “Turing incomplete computer languages”

Here's a copy+paste of an old comment I made on this very subject a couple of years ago. It's very easy to be Turing complete (e.g the x86 MOV instruction), and things that are _not_ Turing complete can still be very useful and powerful. From a previous post of mine: > Turing completeness is neither necessary nor sufficient for a programming language to be useful or interesting. > > A short sampling of non-Turing complete languages: > > * Datalog > * early versions of SQL (though modern versions are) > * markup languages like HTML and Markdown > * regular expressions in the mathematical sense of the term (but see below) > * Agda > * Charity > * Early versions of FORTRAN, as it could not…
19View on Reddit

u/RobertJacobsonin r/compsci • Recommends

On “Is there a name for the things a language needs on top of being 'Turing complete' to be practical?”

Turing completeness is neither necessary nor sufficient for a programming language to be useful or interesting. A short sampling of non-Turing complete languages: * Datalog * early versions of SQL (though modern versions are) * markup languages like HTML and Markdown * regular expressions in the mathematical sense of the term (but see below) * Agda * Charity * Early versions of FORTRAN, as it could not allocate memory dynamically. * LabVIEW and other synchronous programming languages Languages that are often claimed to be non-Turing complete but really are: * Regular expressions in most nontrivial regex libraries * contemporary SQL, including the latest ISO standard * Coq * Idris * [CSS…
3View on Reddit

u/RobertJacobsonin r/ProgrammingLanguages • Recommends

On “Non-turing complete programs”

Turing completeness is easily misunderstood for the reasons given in these comments among others. It's very easy to be Turing complete (e.g the x86 MOV instruction), and things that are _not_ Turing complete can still be very useful and powerful. From a previous post of mine: > Turing completeness is neither necessary nor sufficient for a programming language to be useful or interesting. > > A short sampling of non-Turing complete languages: > > * Datalog > * early versions of SQL (though modern versions are) > * markup languages like HTML and Markdown > * regular expressions in the mathematical sense of the term (but see below) > * Agda > * Charity > * Early versions of FORTRAN, as it co…
3View on Reddit