0
$\begingroup$

This is taken from an old exam of my university that I am using to prepare myself for the coming exam:

Given is a language $\text{Goto}_{17} \subseteq \text{Goto}$. This language includes exactly those $\text{Goto}$ programs in which no constant is ever greater than $17$. Show that every $\text{Goto}$ program can be simulated by a $\text{Goto}_{17}$ program.

$Goto$ here describes the set of all programs written in the $Goto$ language made up of the following elements:

With variables $v_i \in \mathbb{N}$ and constants $c \in \mathbb{N}$
Assignment: $x_i := c, x_i := x_i \pm c$
Conditional Jump: if(Comparison) goto $L_i$
Haltcommand: halt

It seems obvious to me that this would not limit the power of a program, as there are easy ways to just repeat operations to achieve the same thing with limited constants. To add or subtract arbitrary values we can just add or subtract repeatedly. To compare, we can put our value to compare with into a dummy variable and compare, reduce, repeat until we know the value. These dummy variables are guaranteed to be unused and free for this use if we simply map the variables from our Goto program so that any variable $v_i$ from the Goto language maps onto $v_{2i}$ in our new language.

How can the equivalence in power between these to languages be shown? Is a compiler from one to the other the best solution, or are there more elegant ways? Specifically showing how comparisons work seems like it would be rather complicated and this is a question that originally appeared in a written exam with only a few minutes to answer this question if you average it out. If there is no better way, how would an approach to converting the following Goto program into a limited Goto program of this kind look?

v = 99
repeat: v = v + 1
if(v = 100)goto repeat
halt
Improve this question
$\endgroup$
1
  • $\begingroup$ We discourage "please check whether my answer is correct" questions, as only "yes/no" answers are possible, which won't help you or future visitors. See here and here. Can you edit your post to ask about a specific conceptual issue you're uncertain about? As a rule of thumb, a good conceptual question should be useful even to someone who isn't looking at the problem you happen to be working on. If you just need someone to check your work, you might seek out a friend, classmate, or teacher. $\endgroup$
    – D.W. ♦
    Jul 19, 2020 at 8:43

1 Answer 1

Reset to default
1
$\begingroup$

No, that is not a proof. "It seems obvious to me" is not a proof.

To obtain a formal proof, describe an algorithm that, given a Goto program $P$, outputs a Goto$_{17}$ program $P'$, and prove that $P'$ simulates $P$. Basically, you need to construct a compiler that compiles from Goto to Goto$_{17}$, and then prove it correct.

Improve this answer
$\endgroup$
3
  • $\begingroup$ I am still struggling with understanding how such a compiler would then go about compiling a conditional jump using a constant above 17 into one that does not. Any approach I can think of seems overly convoluted and this question was asked in a written exam with very limited time. $\endgroup$
    – Vladis Becker
    Jul 19, 2020 at 9:07
  • $\begingroup$ @VladisBecker, you haven't specified what kinds of conditions are allowed, and you haven't given an example of one that you'd find hard to compile, so I don't know how to answer that. Perhaps you might like to ask a separate question how to compile a specific construct or line or program. $\endgroup$
    – D.W. ♦
    Jul 19, 2020 at 23:32
  • $\begingroup$ @VladisBecker just put the constant into a variable instead. Or subtract equal numbers from both sides of the comparison $\endgroup$
    – user253751
    Apr 11, 2022 at 16:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.