Disan Count

From Esolang
Jump to navigation Jump to search

A Disan Count is a program designed to test whether a programming language can execute infinite loops, conditionals, I/O and basic arithmetic operations successfully. The intention was that any programming language able to implement this function would also be usable to implement a Turing machine [1], allowing a Disan Count to be used to test the Turing completeness of any given language. However, it turned out to be insufficient for this purpose.

History

Disan Counts were proposed by Matías Di Santo by late 2016, as a way to test basic Turing completeness of simple programming languages. As Di Santo explained, any programming language able to implement an arbitrarily long jump cycle effectively could also be used to mimic the movement of an infinite Turing Automata tape. By also introducing means of testing (in)equality and value storage, the read from and write to the tape operations could also be simulated, thus rendering the given language Turing complete.

In response to the definition, languages were created that could perform a Disan Count but fell short of Turing-completeness for other reasons. For example, BuzzFizz is a linear bounded automaton, where the amount of usable memory effectively depends on the size of the input; this technique makes it possible to have enough memory to implement a Disan Count regardless of the size of the input, but not to implement arbitrary Turing machines (because for any computable function from inputs to memory sizes, there's a Turing machine that requires at least that amount of memory, and you can pick a Turing machine whose memory requirements grow too fast with the input for BuzzFizz to handle).

Algorithm

The algorithm is defined as:

n ← input n
a ← 0
Start:
  If a is even:
    print a + "is even!"
  a ← a + 1
  If a < n:
    Jump to Start

For example, in C++ said program could be written as:

int n;
cin >> n;
int a = 0;
while(a < n){
  if(a % 2 == 0) cout << a << " is even!";
  a++;
}

The Disan Count test was defined to disallow 'cheating' the algorithm by increasing the iteration variable by any number other than one, using finite-state loops (like for loops) or avoiding conditionals.

See also

References