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.
