В споре рождается истина

Прощай, матлогика, здравствуй, теория алгоритмов! Правда, это те же яйца, только в профиль.

Я еще заранее решил, что перейду в другую подгруппу, потому что там вела няшная девушка. Она, в принципе, мало чего могла объяснить (в основном фразы вроде “Это так, потому что так написано в методичке лектора”), но какая нафик разница – лектора понять в принципе невозможно.

Облом. Вести теперь будет парень.
Зато он объясняет, причем все понятно, простым русским языком, как для дебилов. Я этому очень рад

Итак, машина с натуральнозначными регистрами, она же МНР.

Это гипотетический дивайс, который имеет бесконечное множество регистров (но, тем не менее, счетное), пронумерованных, начиная с 0: 0, 1, 2, …, N, N+1, … , в каждом из которых может храниться любое натуральное число. Также машина умеет выполнять программы, записанные в виде последовательности команд, которые нумеруются с 1.

Перед началом работы мы задаем начальную конфигурацию МНР – значения регистров.
В процессе работы, МНР что-то делает с содержимым регистров. В итоге она либо останавливается (и тогда мы читаем результат в регистре R[0]), либо.. не останавливается о_О.

Вообще, задать по очереди значения всем регистрам проблематично (их бесконечно много). Но для каждой МНР в частности мы используем лишь ограниченное количество регистров (по крайней мере, нам так сказали.Но я в это не верю и могу написать программу для МНР, которая таки будет использовать все регистры. Подошел к преподу и выяснилось, что в командах можно использовать только жестко зафиксированные константы, но об этом ниже.)
Поэтому мы даем на вход МНР числа (R0, R1, R2, …, RM) и считаем, что регистры с номерами >M содержат 0.

Т.к. в итоге мы берем результат из R[0], то МНР задает функцию f: R^m->R. Логично, что если результатом считать не только R[0], но вообще некоторое число регистров R[0], … R[N], то можно говорить о том, что МНР задает функцию f: R^m->Rⁿ.

Если сказать правду, то одна МНР задает бесконечное количество функций f_q: R^q->Rⁿ, где q = 1, 2, …, W, W+1, … .

МНР понимает 4 команды:

1. Z(i): (zero) обнуляет регистр номер i: R[i]=0
2. S(i): (successor) увеличивет содержимое регистра номер i на 1: R[i]++
3. T(a,b): (transfer) записывает R[b] в R[a]. Куда при этом исчезает старое значение из R[a] – открытый вопрос.
4. J(a,b,c): (jump) если R[a]==R[b], то переходит к команде номер c

При этом нельзя использовать косвенную адресацию, т.е. в команде J можно использовать только константы. Нельзя написать что-то вроде J(0,0,R1), чтобы машина перешла в регистр, адрес которого содержится в R1. Жаль, иначе я все-таки смог бы написать программу, которая перебирает все ячейки

Выполнение программы начинается с команды №1 в списке.
После каждой команды идет переход к следующей, в случае команды J – может произойти прыжок куда-нибудь.
МНР завершает работу, когда пытается выполнить команду, номер которой больше, чем команд в программе.

Если фунция f не опредлена для входного вектора (a0, a1, …, aN), то МНР должна зациклиться с такой начальной конфигурацией.

Некоторые примеры МНР.
Для фунции f(x) = x МНР такая:

1) J(0,0,2)

Для функции f(x) = x+2:

1) S(0);
2) S(0);

Для облегчения тестирования МНР, я написал такой модуль:

// file MNR.cpp
#include "MNR.h"

TCommand commands[M];
int R[N];
int step; // number of current step
int steps_count=0;

void vZ(int a){R[a] = 0; step++;}
void vS(int a){R[a]++; step++;}
void vT(int a, int b){R[a] = R[b]; step++;}
void vJ(int a, int b, int c){if  (R[a]==R[b]) step=c; else step++;}

void J(int a, int b, int c)
{
    step++;
    commands[step].type = tJ;
    commands[step].a = a;
    commands[step].b = b;
    commands[step].c = c;
}
void S(int a){step++;commands[step].type = tS; commands[step].a=a;}
void Z(int a){step++;commands[step].type = tZ; commands[step].a=a;}
void T(int a, int b)
{
    step++;
    commands[step].type = tT;
    commands[step].a = a;
    commands[step].b = b;
}

void Run()
{
    steps_count = step;
    step = 1;
    while (step <= steps_count)
        switch (commands[step].type)
        {
            case tS: vS(commands[step].a); break;
            case tZ: vZ(commands[step].a); break;
            case tJ: vJ(commands[step].a,commands[step].b,commands[step].c); break;
            case tT: vT(commands[step].a,commands[step].b); break;
        }
}

void Input(int arg_c)
{
    int arg, i;
    for (i = 0; i<arg_c; i++)
    {
        printf("Enter arg. no. %d\n", i+1);
        scanf("%i",&arg);
        R[i] = arg;
    }
}

void Output(int arg_c)
{
    int i;
    for (i=0; i<arg_c; i++)
        printf("R[%i] = %i\n", i, R[i]);
}

int bye()
{
    char c;
    printf("Press [Enter] to exit...\n");
    scanf("%c",&c);
    return 0;
}

void RUN(int x,int y){Input(x); Run(); Output(y);}

//file MNR.h
#ifndef MNR_H_INCLUDED
#define MNR_H_INCLUDED
#include <stdio.h>
#define START int main(){
#define END return bye();}
//registers count:
const int N = 20;
//commands count:
const int M = 30;
enum command_type {tZ, tS, tT, tJ};
typedef struct
{
    command_type type;
    int a, b, c;
} TCommand;
void S(int);
void Z(int);
void T(int,int);
void J(int, int, int);
void Input(int arg_c);
void Run();
void Output(int arg_c);
int bye();
void RUN(int,int);
#endif // MNR_H_INCLUDED

Например, если надо написать МНР для функции f(x,y) = x*y, то теперь можно сделать так:

//file main.cpp
#include "MNR.h"
START
J(0,2,9);
S(2);
J(1,3,7);
S(3);
S(4);
J(0,0,3);
Z(3);
J(0,0,1);
T(0,4);
RUN(2,1);
END

Теперь для того, чтобы программа для МНР заработала на компьютере, надо подключить модуль MNR.h,
написать строчку START, набрать программу для МНР (теперь команды нумеровать не надо, но надо ставить после каждой ” ; “), написать строчку RUN(arg_c_input, arg_c_output) (здесь arg_c_input – это размерность вектора на входе, arg_c_output – на выходе) и потом еще написать строчку END.

Во время выполнения, будет предложено ввести входной вектор, а в конце – будет выведен вектор-результат.