13
\$\begingroup\$

A reversible language is a programming language where no operation is capable of destroying information. That means that with the output and a program you can always determine the input provided.

This has some interesting implications for IO. For example in Unbalanced the following program "adds two numbers":

>{[>(}[>{[[>>)

This takes input in the form of

a, b

and outputs

b-1, a+b

Currently this is not a valid addition program because b-1 is output along side the actual output. However since Unbalanced is reversible and addition is not a bijection, a "true addition program" by the sites standards is impossible. In order for the output to be traced back to the input there is always going to be at least one other number on the stack.

It seems like we should allow this. We typically allow languages that always output a bit extra to compete. For example Octave prepends its output with ans =. We allow this because its unavoidable and we want languages like Octave to compete. I believe that the same argument should apply to reversible languages. However if we are not careful in how we allow output for reversible languages we may open up loopholes.

Is there a good way to allow reversible languages to compete in non-bijective challenges?

\$\endgroup\$
4
  • \$\begingroup\$ "That means that with the output and a program you can always determine the input provided." Only if the language prints its entire state. Stack Cats can compute arbitrary functions on the input because only a subset of the state is printed. \$\endgroup\$
    – Martin Ender Mod
    Commented Jul 5, 2017 at 4:41
  • \$\begingroup\$ @MartinEnder I would argue that Stack Cats is not truly reversible for that reason. The implicit output is capable of destroying information. But this is neither here nor there, Stack cats can already answer any question so it doesn't have to be concerned with this question. \$\endgroup\$
    – Wheat Wizard Mod
    Commented Jul 5, 2017 at 4:51
  • \$\begingroup\$ On the matter of Stack Cats - it's reversible, because at program termination, no information is destroyed. The fact that only part of the final state of the information is printed is ancillary. \$\endgroup\$
    – user45941
    Commented Jul 7, 2017 at 13:36
  • \$\begingroup\$ Perhaps, could the reversible language perform any computation, and then also cat out the input? \$\endgroup\$
    – Rohan Jhunjhunwala
    Commented Jul 10, 2017 at 13:18

2 Answers 2

Reset to default
13
\$\begingroup\$

As I see it, the difficulty here is that we need to define a standard output format which is both reversible and unique. A standard output format cannot be allowed to vary with the whims of the programmer as that would be open to abuse. However, if for every input there is a unique legal output which clearly contains the desired value, that should be fine. Thus I propose:

Make a standard output format for reversible languages the input followed by the desired output.

For instance, for the addition challenge:

a, b

becomes

a, b, a+b

This is unique for every input, so it is not open to abuse, and it is guaranteed to be reversible.

\$\endgroup\$
1
  • \$\begingroup\$ And map output 1, 1, 1 to some random input 1qa? \$\endgroup\$
    – l4m2
    Commented Jan 10, 2023 at 9:54
-3
\$\begingroup\$

Answers should comply with the problem specification

Unfortunately, this means that your Unbalanced program would not be valid. The difference between it and the Octave example is that Octave's extraneous output is fixed, while the output from your program will vary.

The problem is that it's simply too complicated to formulate a rule that would 1) allow users to choose subsets of their output to use and 2) not be ripe for abuse (i.e. printing the divmod in a challenge that asks for the remainder).

There are many challenges that cannot be done reversibly. If you want to be able to answer these in a reversible language, your best bet is probably to write an interpreter with a flag that specifies to only use a subset of the output, thus breaking reversibility.

\$\endgroup\$
4
  • 4
    \$\begingroup\$ How is performing divmod in a challenge that asks for the remainder abuse? \$\endgroup\$
    – Wheat Wizard Mod
    Commented Jul 8, 2017 at 0:16
  • \$\begingroup\$ To clarify my last comment, currently the best know way to compute the remainder in brainfuck is a divmod. brainfuck can select which output it cares about because it is capable of destroying information. No one views this as abuse. So why would it be abuse in this case? I'm not arguing that no potential solution might not be abusable, but I don't think that that example is abuse of the rules in anyway. Abuse might be for instance, outputting all the numbers and claiming that the output is somewhere there, that abuse is preventable, but is certainly abuse. \$\endgroup\$
    – Wheat Wizard Mod
    Commented Jul 8, 2017 at 4:47
  • 1
    \$\begingroup\$ @WheatWizard I clarified to mean that it's only abuse if you print both components of the divmod. \$\endgroup\$
    – Esolanging Fruit
    Commented Jul 8, 2017 at 6:59
  • 1
    \$\begingroup\$ If your language cannot do what the challenge asks for, your language is unsuitable for that challenge. That should be the base-line. Specifics on in- or output for a given language on a given challenge should be taken up with the OP, who may not see your extraenious output as a problem. \$\endgroup\$
    – steenbergh
    Commented Jul 10, 2017 at 14:09

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .