В любом случае, можно просто реализовать на машине Тьюринга, это и будет доказательством. А вообще, вот понятная реализация для десятичной системы (взято с cyberforum): q0 -конечное состояние P - пустой символ L - в лево R - в право N - стоим q1 - начальное состояние 1. бежим в конец числа: q1 n->q1 nR q1 P->q2 PL где n от 0 до 9 2. числа от 0 до 4 можно просто умножить, без запоминания 1 q2 - состояние, когда нет единицы для запоминания q2 0->q2 0L q2 1->q2 2L q2 2->q2 4L q2 3->q2 6L q2 4->q2 8L 3. если цифры от 5 до 9, то нужно запомнить 1 и прибавить на следующем шаге q2 5->q3 0L q2 6->q3 2L q2 7->q3 4L q2 8->q3 6L q2 9->q3 8L q3-состояние, когда мы умножаем на 2 и прибавляем 1 к результату 3. если цифры от 0 до 4, то после "избавления" от 1 ничего запоминать не нужно q3 0->q2 1L q3 1->q2 3L q3 2->q2 5L q3 3->q2 7L q3 4->q2 9L 4. если цифры от 5 до 9, то после "избавления" от 1, мы снова ее запоминаем q3 5->q3 1L q3 6->q3 3L q3 7->q3 5L q3 8->q3 7L q3 9->q3 9L 5. заканчиваем программу, когда встречаем пустой символ q2 P->q0 N q3 P->q0 1N если мы все еще помним 1, а уже число закончилось, то на пустой клетке пишем 1.
Программа Вот: Program z1;Var a,b,c,d,k:integer;BeginWriteln('Введите трехзначное число');REadln(a);While a<>0 do beginWriteln('Введите трехзначное число');REadln(a);b:=a div 100 mod 10;c:=a div 10 mod 10;d:=a mod 10;if b+c+d div 10 >0 then writeln('Сумма цифр- двузначное число') else writeln ('Нет, сумма цифр не двузначное число');if b*C*D div 100 >0 then writeln('Произведение цифр- терхзначное число') else writeln ('Нет, произведение цифр не трехзначное число число');Writeln ('Введите любое число');Readln (k);If b*c*d>k then writeln('Произведение цифр больше числа') else writeln('Произведение меньше числа');if B+c+d div 5 =0 then writeln('Сумма цифр числа кратна 5') else writeln ('Сумма цифр не кратна 5');if B+c+d div k =0 then writeln('Сумма цифр числа кратна числу, введенному с клавиатуры') else writeln ('Сумма цифр не кратна числу, введенному с клавиатуры');End;End. Есть маленькая проблема в начале, не помню как прописывать, поэтому число первый раз нужно вводить 2 раза, если не устраевает, можете воспользоваться другими ресурсами
// PascalABC.NET 3.0, сборка 1157 от 02.02.2016 begin var n:=ReadInteger('n='); if n<0 then Writeln(n,'! не определено: n<0') else if n=0 then Writeln('0!=1') else begin var p:BigInteger:=1; for var i:=2 to n do p*=i; Writeln(n,'!=',p) end end.