Kaufmann's NK-automaton

Content

1. What is a Kaufmann's automaton and how does it work?

The NK-automaton is a network of N Boolean logical elements. Each logic element has K inputs and one output. The signals at the inputs and outputs of the elements are binary (they take the values 0 or 1). The outputs of some elements go to the inputs of others, these connections are absolutely random, but the number of inputs K of each element is static. The logical elements are also chosen randomly.

Automaton are autonomous (there are no external inputs). The number of logical elements included in the automaton is assumed to be large, N>1. The automaton functions in discrete time: t = 1,2,3,… The state of the automaton at each moment of time t is determined by the vector X(t) – the totality of the output signals of all logic elements.

In the process of functioning, the sequence of states converges to an attractor - a limit cycle. The sequence of states X(t) in this attractor can be considered as a “program” for the functioning of the automaton.

The number of attractors M and the typical attractor length L are important characteristics of NK-automaton.

2. The task formulation

Input:

  • set n=4, к=2
  • set initial vector (e.g. int v0[] = {1, 1, 0, 1, 0, 0})
  • set a matrix of connections, for example:

    int n[1] = {0, 1, 0, 1, 0, 0};

    int n[2] = {1, 0, 1, 0, 0, 0};

    int n[3] = {0, 1, 0, 1, 0, 0};

    int n[4] = {1, 0, 0, 0, 0, 1};

    int n[5] = {0, 0, 0, 0, 1, 1};

    int n[6] = {0, 0, 1, 0, 1, 0};

  • It is also necessary to describe the logical elements.

Output:

  • number of different attractors.

3. The solution of the problem

For a Python solution, you can visit my repository.
Ian L. Dolganov
Ian L. Dolganov
Student of Applied Informatics

My research interests are in OS administration and various programming languages.