Results 1 to 6 of 6

Math Help - Counting

  1. #1
    Member
    Joined
    May 2006
    Posts
    148
    Thanks
    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.

    Thanks for your help.

    Under ordinary situations, it would just be 6! I am assuming?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Senior Member
    Joined
    Jun 2005
    Posts
    295
    Awards
    1
    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"?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote 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
    Last edited by CaptainBlack; May 7th 2006 at 06:31 AM.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Member
    Joined
    May 2006
    Posts
    148
    Thanks
    1
    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.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Member
    Joined
    May 2006
    Posts
    148
    Thanks
    1
    Anyone?
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Senior Member
    Joined
    Apr 2006
    Posts
    399
    Awards
    1
    Quote 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 6^{n-2} because any instruction can be repeated.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. counting 1
    Posted in the Statistics Forum
    Replies: 1
    Last Post: September 8th 2011, 09:01 AM
  2. Counting
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: May 9th 2010, 05:34 AM
  3. Counting
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: March 9th 2010, 06:19 PM
  4. help on Counting
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: October 25th 2009, 09:51 AM
  5. Counting
    Posted in the Algebra Forum
    Replies: 2
    Last Post: August 10th 2009, 06:32 PM

Search Tags


/mathhelpforum @mathhelpforum