4
$\begingroup$

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.

$\endgroup$
5
  • 1
    $\begingroup$ Gonna need to find some way to iterate just to get to primitive recursive functions. If you want to get to Turing completeness then I'd first try to find a way to create an infinite loop. I know it has sums (and maybe products?) but I don't think that's enough to even get all primitive recursive functions. Summation on its own doesn't give you a way to create an infinite loop though so you need something extra for Turing completeness. $\endgroup$
    – Jake
    Sep 12 at 0:53
  • $\begingroup$ @Jake I also mentioned Actions. This feature includes a 'ticker', which loops a series of statements forever. Since statements can be conditional, this could allow loops. $\endgroup$
    – emanresu A
    Sep 12 at 0:56
  • 1
    $\begingroup$ If it allows big integers, unlimited iteration, and variables that change on each iteration then it is Turing complete for sure $\endgroup$
    – Jake
    Sep 12 at 1:04
  • 4
    $\begingroup$ I don't think this question is a good fit in its current form because it requires us to completely understand everything supported by Demos. I think it would be better to make the question self-contained by listing all relevant operations that Demos supports, or by identifying a core subset of Demos that you can describe in a self-contained way. Without recursion or loops or fixpoints, it's unlikely to be Turing-complete; with them, it will be, as @Jake states. You might also be interested in en.wikipedia.org/wiki/…. $\endgroup$
    – D.W.
    Sep 12 at 1:09
  • $\begingroup$ @D.W. I'll edit in more stuff. $\endgroup$
    – emanresu A
    Sep 12 at 4:33
7
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ Nice! Just one thing - you don't need a registered account anymore - The ticker just only appears as an option if you have an existing action. $\endgroup$
    – emanresu A
    Sep 13 at 7:34
  • $\begingroup$ @emanresuA That's kinda weird, since it doesn't really need one-off actions to build an interesting ticker simulation. $\endgroup$
    – Bubbler
    Sep 13 at 7:38
  • $\begingroup$ Worth noting that functions taking only numbers as arguments isn't a deal-breaker: you can imagine Gödel encoding the function to be applied. $\endgroup$
    – cody
    Sep 14 at 19:54
  • $\begingroup$ What about infinite sliders? Desmos has different modes for sliders, one of them is infinitely increasing? $\endgroup$
    – PyGamer0
    Sep 15 at 9:35
  • $\begingroup$ @pVCaecidiosporeadduced I haven't been able to make a slider infinitely increasing. How do I do that? Anyway it doesn't change the conclusion that it (without actions) is not Turing-complete. $\endgroup$
    – Bubbler
    Sep 15 at 22:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.