Lucid

I’ve been watching the Turing completeness of Lucidchart for over a year now. As far as I have been able to prove, Lucidchart has been dipping in and out of being Turing complete for most of that time. In the past, however, I have been able to simulate Turing machines only through the exploitation of bugs. All of my previous proofs lie in broken states, doomed by the patches that fixed the bugs they relied on. This time, I can prove that Lucidchart is Turing complete—and it isn't a fluke. Custom data is a less publicized, and still very rough, feature of Lucidchart. It allows spreadsheet-like formulas on shapes, but with more relational capabilities, since diagrams are often about relationships. (Read this article to learn more about this feature.) Custom data is the feature that makes Lucidchart Turing complete. Also, as a side note, all of the features used in this Turing complete “proof” are available to free Lucidchart users.

Lucidchart is focused around visual communication, so it made sense to me to prove Lucidchart’s Turing completeness in the most visual way possible. I settled with implementing Conway’s Game of Life.

Conway’s Game of Life running in the Lucidchart editor (sped up 6x)

How it works

All the formulas in a Lucidchart document are evaluated as soon as their value is requested and one of the formulas dependencies have changed. This immediate invalidation of the dependency tree necessitates the detection of, and erroring upon, any cyclic dependency to prevent infinite loops. Meaning, at first, there doesn’t seem to be a good way to store a previously calculated value in memory and then use that stored value in the next calculation. In spite of that, there are a few built-in functions in Lucidchart that make it possible. The two branches of an IF function are lazily evaluated. So A can depend on B and B can depend on A—if they don’t depend on each other at the same time. For example, if the formula for A was @B and the formula for B was @A, it would result in an error because of the direct circular dependency.

However, if A were IF(true, @B, 5) and B was IF(false, @A, 20), then there would be no circular dependency. This isn’t very useful on its own, but it is a stepping stone to simulating a flip-flop.

The very high-level idea of a flip-flop is that during a clock cycle, the flip-flop will read the current input, store the value of the input, and then allow the stored value to be read during the next cycle. To simulate that in Lucidchart, we need a clock cycle to alternate between the calculation and storage phases.

Lucidchart has been able to show the current time on a document for years. Luckily, that concept made its way into formulas with the CURRENTSECOND function. With the CURRENTSECOND function and the ISODD or ISEVEN functions, we can simulate a two-second clock cycle (an astounding .5 hz!)—an even second for the first phase of the cycle and an odd second for the second phase of the cycle.

Valid Circular Dependency with Clock Cycle

Valid Circular Dependency with Clock Cycle Evaluated

The last missing piece is being able to read the value that was “stored” during the storage phase of the cycle. This is where the bug exploitation originally came into play. At certain points, there were a couple of holes in the dependency graph that allowed the result of a formula to be “stored” within another feature in Lucidchart, such as through conditional formatting or by adding the text to the shape. The formula was then able to read the calculated value back out from that feature. Unfortunately, those were legitimate bugs that needed to be fixed—holes in the dependency graph meant that formulas may not always recalculate when they should. Recently, with the overwhelming approval of our CTO—and much to the chagrin of our chief architect—I added the LASTCALCULATEDVALUE built-in function. This function made what was once accidentally Turing complete officially Turing complete.

Valid Circular Dependency with Clock Cycle and Last Calculated Value

Valid Circular Dependency with Clock Cycle and Last Calculated Value Evaluated

By using those functions, plus other functions that allow you to read the values of the shapes connected via lines, and adding in some conditional formatting, I was able to implement Conway’s Game of Life in Lucidchart. Building it took several hours and involved drawing 2884 total shapes and lines. You can play around with, and see the final formulas for, a small version of it by clicking here, or on the image below.

Small Conway's Game of Life — Smaller Implementation of Conway's Game of Life in Lucidchart

DISCLAIMER: Building complex formulas within Lucidchart, at the time of writing, can be painful. Good public documentation for custom data and formulas is coming soon. The current documentation can be found here.

Image of Building Conway's Game of Life in Lucidchart — Building Conway's Game of Life in Lucidchart

Lucidchart is Turing Complete

How it works

About Lucid