Program that accepts inputs of the form 1^n 2^{n^2} 0

  • Context: MHB 
  • Thread starter Thread starter mathmari
  • Start date Start date
  • Tags Tags
    Form Program
Click For Summary

Discussion Overview

The discussion revolves around the development of a RAM program designed to accept inputs of the form $1^n 2^{n^2} 0$. Participants are exploring the logic and structure of the program, addressing specific input cases, and refining the code to ensure it functions correctly according to the specified input format.

Discussion Character

  • Technical explanation
  • Debate/contested
  • Mathematical reasoning

Main Points Raised

  • Some participants propose a structure for the RAM program that includes reading inputs and counting occurrences of '1's and '2's.
  • Others question whether specific inputs, such as 1212220 and 1134560, will be accepted by the program.
  • There is a discussion about ensuring that all '1's appear before any '2's in the input string for acceptance.
  • Some participants express concerns about the program's behavior when inputs are not accepted, noting inconsistencies in outputs (sometimes returning 0, sometimes returning nothing).
  • Participants debate the appropriate use of JZERO and JGTZ instructions in the program, with some suggesting that JZERO should be used to test for inequality.
  • There is a proposal to include additional conditional statements to handle specific cases in the program logic.

Areas of Agreement / Disagreement

Participants generally agree on the need for the program to accept inputs in a specific format, but there are multiple competing views on the implementation details and the behavior of the program with certain inputs. The discussion remains unresolved regarding the exact structure and logic of the RAM program.

Contextual Notes

There are limitations related to the assumptions made about input formats and the behavior of the RAM program under various conditions. Some mathematical steps and logical conditions remain unresolved, particularly concerning the handling of specific input cases and the appropriate use of instructions.

mathmari
Gold Member
MHB
Messages
4,984
Reaction score
7
Hey! :o

I have to write a RAM program to accept all inputs of the form $1^n 2^{n^2} 0$.

The instructions of the RAM machine are the following:

LOAD a ; c(0) ← v(a), c(i) is the integer stored in register i (the contents of register i), v(a) is the value of operand a
(v(=i)=i, v(i)=c(i), v(*i)=c(c(i)) )

STORE i ; c(i) ← c(0)
STORE *i ; c(c(i)) ←c(0)

ADD a ; c(0) ← c(0)+v(a)

SUB a ; c(0) ← c(0)-v(a)

MULT a ; c(0) ← c(0) × v(a)

DIV a ; c(0) ← ⌊c(0)/v(a)⌋

READ i ; c(i) ← current input symbol
READ *i ; c(c(i)) ← current input symbol. The input tape head moves one square right in either case.

WRITE a ; v(a) is printed on the square of the output tape currently under the output tape head. Then the tape head is moved one square right.

JUMP b ; The location counter is set to the instruction labeled b.

JGTZ b ; The location counter is set to the instruction labeled b if c(0)>0; otherwise, the location counter is set to the next instruction.

JZERO b ; The location counter is set to the instruction labeled b if c(0)=0; otherwise, the location counter is set to the next instruction.

HALT ; Execution ceases.


I have done the following:

Code: 
Read x from input
d=0, s=0
while x!=0
       if x-1=0
           d=d+1
       else
           s=s+1
       Read x from input
p=d*d
r=s-p
if r=0
   Write 1

Then the RAM program is the following:

Code: 
READ 1

LOAD =0
STORE 2

LOAD =0
STORE 3

while: LOAD 1
       JZERO endwhile 

LOAD 1
SUB =1
JGTZ two

LOAD 2
ADD =1
STORE 2

two: LOAD 3
     ADD =1
     STORE 3

READ 1

endwhile:  LOAD 2
           MULT 2
           STORE 4

           LOAD 3
           SUB 4
           STORE 5

LOAD 5
JZERO output
HALT
output: WRITE =1
        HALT

Is this correct?? (Wondering)
 
Technology news on Phys.org
Hi! (Smile)

mathmari said:
I have to write a RAM program to accept all inputs of the form $1^n 2^{n^2} 0$.
Code: 
Read x from input
d=0, s=0
while x!=0
       if x-1=0
           d=d+1
       else
           s=s+1
       Read x from input
p=d*d
r=s-p
if r=0
   Write 1

Suppose we give the input 1212220.
Will it be accepted? (Wondering)

And what happens to 1134560? (Wondering)
 
I like Serena said:
Suppose we give the input 1212220.
Will it be accepted? (Wondering)

It will be accepted... (Doh)

So, we have to make sure that an input will be accepted if all $1$'s are all together at the beginning of the string and then the $2$'s follow, right?? (Wondering)

I like Serena said:
And what happens to 1134560? (Wondering)

And the program has to accept only the symbols $1$ and $2$, right?? (Wondering)

I tried it again... (Nerd)

Code: 
Read x from input
d=0, s=0
while x-1=0
    d=d+1
    Read x from input
while x-2=0
    s=s+1
    Read x from input
if x=0
    p=d*d
    r=s-p
    if r=0
       Write 1
else
    Write 0

Is it better now?? (Wondering)
 
mathmari said:
So, we have to make sure that an input will be accepted if all $1$'s are all together at the beginning of the string and then the $2$'s follow, right?? (Wondering)

And the program has to accept only the symbols $1$ and $2$, right?? (Wondering)

Right! (Nod)
I tried it again... (Nerd)
Code: 
Read x from input
d=0, s=0
while x-1=0
    d=d+1
    Read x from input
while x-2=0
    s=s+1
    Read x from input
if x=0
    p=d*d
    r=s-p
    if r=0
       Write 1
else
    Write 0
Is it better now?? (Wondering)

Much better! (Nod)

Still, if the input is not accepted, we now sometimes get 0 and sometimes we get nothing at all. (Worried)
 
I like Serena said:
Still, if the input is not accepted, we now sometimes get 0 and sometimes we get nothing at all. (Worried)

Why do we get sometimes nothing at all?? (Wondering)
 
mathmari said:
Why do we get sometimes nothing at all?? (Wondering)

What happens with 11220? (Wondering)
 
I like Serena said:
What happens with 11220? (Wondering)

Is it maybe as followed?? (Wondering)

Code: 
Read x from input
d=0, s=0
while x-1=0
    d=d+1
    Read x from input
while x-2=0
    s=s+1
    Read x from input
if x=0
    p=d*d
    r=s-p
    if r=0
       Write 1
    else
       Write 0
else
    Write 0
 
mathmari said:
Is it maybe as followed?? (Wondering)

Code: 
Read x from input
d=0, s=0
while x-1=0
    d=d+1
    Read x from input
while x-2=0
    s=s+1
    Read x from input
if x=0
    p=d*d
    r=s-p
    if r=0
       Write 1
    else
       Write 0
else
    Write 0

That will do the trick!
Good! (Sun)
 
I like Serena said:
That will do the trick!
Good! (Sun)

Great! (Happy)

So, is the RAM program the following?? (Wondering)

Code: 
READ 1

LOAD =0
STORE 2

LOAD =0
STORE 3

while1: LOAD 1
       SUB =1
       JGTZ endwhile1 

LOAD 2
ADD =1
STORE 2

READ 1

JUMP while1

endwhile1: while2: LOAD 1
                   SUB =2
                   JGTZ endwhile2

LOAD 3
ADD =1
STORE 3

READ 1

JUMP while2

endwhile2:  LOAD 1
            JGTZ N
           
LOAD 2          
MULT 2
STORE 4

LOAD 3
SUB 4
STORE 5

LOAD 5
JZERO output
WRITE =0
HALT
output: WRITE =1
        HALT

N: WRITE =0
   HALT
 
  • #10
mathmari said:
Great! (Happy)

So, is the RAM program the following?? (Wondering)

Code: 
READ 1

LOAD =0
STORE 2

LOAD =0
STORE 3

while1: LOAD 1
       SUB =1
       JGTZ endwhile1 

LOAD 2
ADD =1
STORE 2

READ 1

JUMP while1

endwhile1: while2: LOAD 1
                   SUB =2
                   JGTZ endwhile2

LOAD 3
ADD =1
STORE 3

READ 1

JUMP while2

endwhile2:  LOAD 1
            JGTZ N
           
LOAD 2          
MULT 2
STORE 4

LOAD 3
SUB 4
STORE 5

LOAD 5
JZERO output
WRITE =0
HALT
output: WRITE =1
        HALT

N: WRITE =0
   HALT

You have a couple JGTZ's in there that I think should be JZERO's. (Worried)

And I think WRITE =0 is not an allowed instruction. (Wasntme)
 
  • #11
I like Serena said:
You have a couple JGTZ's in there that I think should be JZERO's. (Worried)

Why should they be JZERO?? (Wondering)

The loop is executed while [m]x-1=0[/m].
So, it goes to endwhile when [m]x-1>0[/m], or not??
I like Serena said:
And I think WRITE =0 is not an allowed instruction. (Wasntme)

Why isn't it an allowed instruction?? (Wondering)

So, should I just write [m]HALT[/m]??
 
  • #12
mathmari said:
Why should they be JZERO?? (Wondering)

The loop is executed while [m]x-1=0[/m].
So, it goes to endwhile when [m]x-1>0[/m], or not??

It is supposed to go to endwhile when [m]x-1≠0[/m].
That is different, is it not? :confused:More to the point, suppose your input is $1121110$.
What will happen in your RAM code? (Wondering)
Why isn't it an allowed instruction?? (Wondering)

Mmh... I guess it is allowed.
I had the impression that WRITE needed to have the number of a register as parameter.
But rereading the spec, I guess it can also be an actual number. (Blush)
 
  • #13
I like Serena said:
It is supposed to go to endwhile when [m]x-1≠0[/m].
That is different, is it not? :confused:

JZERO endwhile means that the location counter is set to the instruction labeled endwhile if c(0)=0; otherwise, the location counter is set to the next instruction.

And JGTZ endwhile means that the location counter is set to the instruction labeled endwhile if c(0)>0; otherwise, the location counter is set to the next instruction.

So, which of them do we have to use?? (Wondering)

I like Serena said:
More to the point, suppose your input is $1121110$.
What will happen in your RAM code? (Wondering)

Do we have to use an if statement after the second while ??

Code: 
if x-1=0
   Write 0

(Wondering)
 
  • #14
mathmari said:
JZERO endwhile means that the location counter is set to the instruction labeled endwhile if c(0)=0; otherwise, the location counter is set to the next instruction.

And JGTZ endwhile means that the location counter is set to the instruction labeled endwhile if c(0)>0; otherwise, the location counter is set to the next instruction.

So, which of them do we have to use?? (Wondering)

You are testing for "greater than", when the test should be for "inequality".
I suggest using JZERO to implement a test for inequality.
Do we have to use an if statement after the second while ??

Code: 
if x-1=0
   Write 0

(Wondering)

Let's see... (Thinking)

You have:
Code: 
while x-1=0
  do statements

How about encoding it with:
Code: 
while:
  SUB =1
  JZERO do
  JUMP endwhile
do:
  statements
  JUMP while
endwhile:
(Wondering)
 
  • #15
I like Serena said:
You are testing for "greater than", when the test should be for "inequality".
I suggest using JZERO to implement a test for inequality.
We have

Code: 
while x-1=0
    d=d+1
    Read x from input

So, isn't the while loop executed while [m]x-1=0[/m] ?? (Wondering)

When we write

Code: 
JZERO endwhile

doesn't this mean that the while loop ends when [m]x-1=0[/m] ?? (Wondering)

Or haven't I understood it right?? (Wondering)
 
  • #16
mathmari said:
We have

Code: 
while x-1=0
    d=d+1
    Read x from input

So, isn't the while loop executed while [m]x-1=0[/m] ?? (Wondering)

Yes... (Thinking)

When we write

Code: 
JZERO endwhile

doesn't this mean that the while loop ends when [m]x-1=0[/m] ?? (Wondering)

Or haven't I understood it right?? (Wondering)

Also true.
That's why we should use [m]JZERO do[/m] instead, meaning we jump to the do-part of the while loop instead of the end of the while loop. (Wasntme)
 

Similar threads

MHB Converting Recursion into Loops for Computing n^n
  • · Replies 15 ·
Replies
15
Views
3K
MHB Read numbers and print them in sorted order
  • · Replies 8 ·
Replies
8
Views
2K
Python Partial pivoting in getting the reduced row echelon form of a matrix
  • · Replies 2 ·
Replies
2
Views
2K
Character pattern program -- Print large words using "X" characters
  • · Replies 12 ·
Replies
12
Views
3K
Is this computability theory proof correct?
  • · Replies 1 ·
Replies
1
Views
2K
Adding 2 and 3 digit capacity for assembly program
  • · Replies 4 ·
Replies
4
Views
5K
Python Simple code example of transforming matrix into upper triangular form
  • · Replies 3 ·
Replies
3
Views
2K
C/C++ Matrix33 in C++: Create, Add, Check & Program
  • · Replies 25 ·
Replies
25
Views
3K
Python Python: Semidefinite program with CVXPy 'Error parsing inputs'
  • · Replies 2 ·
Replies
2
Views
2K
Fortran Errors in Fortran code for solving Laplace's equation in 3D
  • · Replies 4 ·
Replies
4
Views
3K