Нужна помощь по дискретной математике в решении задач Опции

[computersha]

<адрес удален> Помогите пожалуйста срочно решить задачи по дискретке!!
тема: "Программа машин Поста" (там шесть видов команд стандартных - i U j, i стоп и т.д.)
1) Подсчитать количество различных программ длины 2.
2) Написать программу бессмертного глобального вируса, уничтожающего ленту, на которой галочки и пустые места стоят как угодно далеко и справа и слева.
3) Написать программу глобального бессмертного вируса, который уничтожает любую ленту.
4) Написать программу удвоения массива, изображающего число.
Пожалуйста, это невероятно важно!! (сколько сможете) мыло <сколько можно говорить: публикация адресов запрещена! Lapp>

Извините, что влезла в вашу тему "Дискретная математика, нужна помощь", я никогда раньше не была на форумах.

[Lapp]

там шесть видов команд стандартных - i U j, i стоп и т.д.)

Считаю, что эти команды такие:

n L j - сместиться влево
n R j - сместиться вправо
n 0 j - стереть метку
n 1 j - поставить метку
n ? j1, j0 - условный переход
n Stop

n - это номер (адрес) строки.
j - адрес перехода. Если j не указано, то переход на следующую строку.

1) Подсчитать количество различных программ длины 2.

Вопрос: что считать различными программами? Если различными по коду, то тогда примерно такое рассуждение:

6*6 различных наборов команд
из них 5+5=10 содержат 1 Stop
и одна содержит два стопа
Все команды, кроме Stop, могут иметь адрес перехода 1 или 2. То есть их число увеличивается в два раза, за вычетом 11.
Команда ? имеет два адреса. То есть 5+5=10 команд нужно еще удвоить.
А программа, состоящая из двух ? еще раз удваивается.. значит, еще плюс 2.
Таким образом, всего:

6*6 + (6*6-10-1) + 10 + 2 = 6*6*2 + 1 = 73.
Ищите у меня ошибки в комбинаторике и арифметике .

2) Написать программу бессмертного глобального вируса, уничтожающего ленту, на которой галочки и пустые места стоят как угодно далеко и справа и слева.
3) Написать программу глобального бессмертного вируса, который уничтожает любую ленту.

Я что-то не улавливаю разницы в этих двух вопросах.. Вот, написал прогу, которая просто стирает все метки с ленты.

Код

1  R
2  ?  3, 1
3  0
4  L
5  ?  6, 4
6  0  1

Она действительно бессмертная, если лента бесконечная в обе стороны .

4) Написать программу удвоения массива, изображающего число.

Как я понял, нужно умножить число на два. Вот программа.
Предполагаем, что перед началом каретка стоит на самой левой единице. Также преполагаем, что слева от числа есть достаточно свободного места.

Код

1  ?  3, 2  
2  Stop
3  0
4  L
5  ?  4, 6
6  1
7  R
8  ?  7, 9
9  1
10 R

Спасибо за задачку! развлекся немного, узнал про машину Поста..

[-computersha-]

Большущее спасибо, Lapp!!! Даже не надеялась, что кто-то ответит!

[-computersha-]

Сорри, смайлик, показывающий язык случайно нажала!:)
P.S.: В принципе, все задания более менее понятны за исключением первого, где ты говоришь о комбинаторике, т.к. на лекциях о таком нам не говорили пока еще. И мне поэтому не ясно по какой формуле это вычисляется. И сам ход рассуждений тоже.
P.P.S.: Я в этом просто не очень разбираюсь.