1. ## Counting

Hello, I was wondering if someone could help me with these two counting problems.

"There is a simple programming language known as TRIVIAL. In this language only the following 6 types of instructions are allowed:
a.) Input X, a natural number
b.) Go to step # -
c.) Set X := X + 1
d.) If X = 0, then go to step # -
e.) If > 0, then set X := X - 1
f.) Stop.

Suppose that a program must begin with the instruction Input X and end with the instruction Stop. How many different programs are there, written in the language TRIVIAL if the program is n steps long?"

Similar to the first, the next is: "Suppose that a TRIVIAL program can begin with one or more statements Input X, where X may be any letter of the alphabet; for example, we may begin with Input A and then following with Input B. Then we allow statements of the form A := A + 1, and if B > 0, then set B := B - 1, and so on, provided that A and B are input variables. If the program begins by reading in two variables A and B, then how many different trivial programs are there using n steps?"

In this one, need to take into account 26 letters and im assuming combinatorics.

Under ordinary situations, it would just be 6! I am assuming?

2. You're going to need to say what you mean by "different". So you mean that they execute different functions (so that any two programs which produce the same output on the same input are the same), or execute different sequences of instructions, or are verbally different.

To put it concretely:
The programs
Code:
1. Input X
2. Goto 3
3. Set X = X+1
4. Stop
and
Code:
1. Input X
2. Set X = X+1
3. Goto 4
4. Stop
both produce the function X -> X+1. Are they "different"?

3. Originally Posted by rgep
You're going to need to say what you mean by "different". So you mean that they execute different functions (so that any two programs which produce the same output on the same input are the same), or execute different sequences of instructions, or are verbally different.
You might also ask that the programs terminate.

Looking at the language definition, I suspect TRIVIAL is sufficiently
complex to simulate a Turing Machine - which may well open up a whole
new can of worms

On second thought maybe not quite - you might need an instruction
like

If X==N goto step #

N a natural number to simulate a TM

RonL

4. I would say that they are different programs because the steps are different. They may be "isomorphic" in that they produce the same results but they are not the same program.

5. Anyone?

6. Originally Posted by fifthrapiers
"There is a simple programming language known as TRIVIAL. In this language only the following 6 types of instructions are allowed:
a.) Input X, a natural number
b.) Go to step # -
c.) Set X := X + 1
d.) If X = 0, then go to step # -
e.) If > 0, then set X := X - 1
f.) Stop.

Suppose that a program must begin with the instruction Input X and end with the instruction Stop. How many different programs are there, written in the language TRIVIAL if the program is n steps long?"

Under ordinary situations, it would just be 6! I am assuming?
I'd say $\displaystyle 6^{n-2}$ because any instruction can be repeated.