Is Desmos Turing-Complete?

Question

The graphing calculator Desmos has a ton of functions, and can express any arithmetric formula. What I want to know is, is it Turing-Complete?

Desmos supports, among other things:

• Most mathematical operations / functions
  • Multiplication, addition, subtraction, division, modulo, etc
  • Sum and product
  • Integration and differentiation
• Variables
• Non-recursive functions
• Actions, basically functions that modify the global state
• Conditionals

However, the global state is static - Actions and user interaction are the only thing that can modify this.

The only way of looping is through the ticker, a recent feature that executes an action at set intervals. For example, this calculates the factorial through looping, by multiplying a by b and decrementing b until b is 0. Multiple actions can be put in the ticker, separated by commas.

Answer 1

I tried various things with Desmos and came to the following conclusions:

Desmos without Actions is not Turing-complete.

• All built-in functions are halting (basically since they are mathematical in nature).
• Variable assignment is halting. (A variable can hold either a number or a list of numbers, nothing else.)
• All function definitions are halting. Recursive definition is not allowed, so I tried to simulate something like a fixed-point combinator, but a function parameter can only be a number or a list (function is not allowed) so this is impossible.
• A conditional in Desmos is officially called a piecewise function which is in the form of {cond1:value1, cond2:value2, [default]}. All branches should evaluate to a number or a list, and they are evaluated eagerly. No means to introduce a loop here.
• You can introduce a bounded loop on a variable in the form of (min, max, step). But both min and max should be a finite number, and setting step to 0 does not actually set the step size to zero. Therefore, you cannot introduce an infinite loop using this feature.

Therefore, any "program" in Desmos without Actions always halts, which means it is not TC.

Edit: @pVC noted that a slider can be infinitely increasing. I haven't been able to reproduce it, but its addition does not change the conclusion since it does not allow any kind of global state to be shared between each iteration (without Actions, we don't have any global variables we can modify within each iteration). It is trivially impossible to make the loop halt, and again the Halting problem is solved.

Desmos with Actions is Turing-complete.

(Side note: Using Actions requires a registered account. The doc says so, but apparently it's not.)

The most important feature that matters here is Tickers, which adds the ability to introduce an infinite loop. It is almost thoroughly documented, but a crucial piece that is missing is that, if you use a piecewise function with actions as branches and omit the default branch, the entire simulation halts when it hits the default branch.

This, combined with the support for numbers and lists, is enough to easily simulate some of the minimalist TC languages such as

• Tag system, especially a version with an explicit halt symbol
  • Example: Set the ticker action to {s[1]=1: s->join(s[3...],[2,2,1,0]), s[1]=2: s->join(s[3...],[2])} with the initial condition of s being a list of 1 and 2's
• FRACTRAN
  • Example: Set the ticker action to {mod(f,2)=0: f->3f/2, mod(f,3)=0: f->2f/3} with the initial condition of f being a positive integer
  • Works only theoretically, because Desmos uses JS numbers under the hood which has limited precision (which is why I included tag systems as a more concrete proof)

Therefore Desmos with Actions is TC.

Answer 2

This may be an old topic but using regressions you can repeatedly redefine variables (I think it's 60FPS).

Basic tutorial:

Step 1:

copy and paste this into a new desmos session:

v_{ariable}=0
V_{ariable}~v_{ariable}+1

Step 2:

copy and paste this into both slider bounds of v_{ariable}=0:

V_{ariable}

Step 3:

Press play on what is now v_{ariable}=1

Example of usage: https://www.desmos.com/calculator/vtogi0kp5t

More information: https://www.reddit.com/r/desmos/wiki/regression_bug