Turing-Complete polyglot

7

Write a polyglot (code that works in two or more languages) that has a "mid-section" that can be modified to do any computational task. This question is similar to https://stackoverflow.com/questions/1053931/code-golf-shortest-turing-complete-interpreter.

Rules:

The program must be able to preform a computation and print the results. Pseudorandom number capability is a plus but not necessary. The results must be the same in all languages, minor string-formatting differences are OK.

There is a section in the program that can be modified (in a straight-forward way) to do any computation (Turing complete). This is like the "comments section" in http://ideology.com.au/polyglot/polyglot.txt for which any comment can be inserted.

You must use at least 2 languages (this rule is here so you don't sue me).

Edit: Ideally you only need to write the "computation" part once. It is less interesting to use comment blocks, etc to knock out A so you have a block from B and then knockout B to write code from A. However, the one block solution is very difficult unless the languages have enough "overlap".

Also, using very similar languages (like C# and Java) isn't as interesting. It is still allowed but will probably earn less votes.

Grading

The winning is a popularity contest (Mar 1st).

Kevin Kostlan

Posted 2014-02-24T01:01:21.657

Reputation: 289

Question was closed 2018-02-02T04:38:58.347

2What's your winning criterion? – TheDoctor – 2014-02-24T01:02:34.960

1Just made it a popularity contest, easy to do. – Kevin Kostlan – 2014-02-24T01:05:43.740

3Why the 2 languages rule and how different do they have to be? Can we use C, C++, C# (and possibly Java)? (Would that be 4 languages?) ..... Ok as it's a popularity contest I guess the mob could decide that one, but I will make the point anyway. – Level River St – 2014-02-24T05:46:13.947

1Do python 2 and python 3 count as different languages? – TheDoctor – 2014-02-24T16:32:55.970

Answers

4

Ruby and Spidermonkey JS

i=0
r=rand
=begin
=Math.random(); n=print;
var end=''; y
=end
//=~''; def n(x); puts x; end

while ((i+=1) < 5)
  if (i%2==0) 
    n('Hi!')
  else 
    n('Bye!')
  end;
end;

a=17*r
n(a);

This works because...

  • rand is random in Ruby, but a variable in JS that gets assigned to Math.random(). A slight improvement would be assigning JS's rand to Math.random so that you can execute rand() in both.
  • =begin...=end is a comment block in Ruby and assignment in JS
  • The middle part is polyglot. If you gave the list of any functions you'd like, I'd def them in Ruby so they are the same as the JS ones or possibly define them in JS.
  • end, needed to end code blocks in ruby is now defined as '' in JS.
  • while is the same in both languages, as is +=, ==, -=, *, -, +, =, %, /, 'strings'
  • // is the start of a comment in JS but a regex in Ruby.
  • n is defined in Spidermonkey JS to be print (which outputs to stdout). In Ruby, I redefined it to be puts, much the same. If I weren't in a mindset, I would have def print(x) instead of n(x).
  • No use of polyglot comments!

Not that Charles

Posted 2014-02-24T01:01:21.657

Reputation: 1 905

1If you can increment and decrement variables, and have at least two variables that store bignum integers available, while is sufficient. That's the simplest Turing Complete construction using the sort of primitives you have here. – None – 2016-12-09T22:55:23.103

"The middle math part is polyglot". Is there enough overlap in the languages for the middle part to be turing complete? – Kevin Kostlan – 2014-02-24T14:51:47.103

I missed that. What are your requirements for completeness? This is an incredibly undefined question. We have */%-+(), and I can work on an if/else based on <,>,==. Is there anything else lacking? – Not that Charles – 2014-02-24T15:18:35.717

2"turing complete" is not ill defined. You would also need to have some sort of while/for loops in order to qualify. – Kevin Kostlan – 2014-02-27T02:51:28.357

1@KevinKostlan Ok - got single-line while and if/else. Is that sufficient? – Not that Charles – 2014-02-27T04:58:51.770

10

C, Python, and Brainfuck

The Brainfuck program on the line starting with pgm= can be changed into any valid Brainfuck program (so it is Turing-complete). The program will then run in C, Python, and Brainfuck. The given program prints Hello World!.

The interpreters in both C and Python have the following characteristics:

  • 8-bit cells
  • Infinite tape in both directions
  • -1 (255) on EOF

It runs like this:

$ gcc poly_bf.c; ./a.out
Hello World!
$ python poly_bf.c
Hello World!
$ bf poly_bf.c
Hello World!

And here's the program:

#define AA [
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define BB ]
#define PGM char*\
pgm="++++++++[>++++[>++>+++>+++>+<<<<-]>+>+>->>+[<]<-]>>.>---.+++++++..+++.>>.<-.<.+++.------.--------.>>+.>++.";
#define ZZ \
""" [-][";
struct cell { char val; struct cell *prev; struct cell *next; };
struct cell *prv(struct cell *c) { 
    if (!c->prev) {
        struct cell *z = malloc(sizeof(struct cell));
        z->next = c;
        z->prev = 0;
        z->val = 0;
        c->prev = z;
    }
    return c->prev;
}
struct cell *nxt(struct cell *c) {
    if (!c->next) {
        struct cell *z = malloc(sizeof(struct cell));
        z->prev = c;
        z->next = 0;
        z->val = 0;
        c->next = z;
    }
    return c->next;
}
int main() { 
    PGM
    int ip=0, t=0;
    struct cell *c = malloc(sizeof(struct cell));
    memset(c, 0, sizeof(struct cell));
    while (pgm[ip]) {
       switch(pgm[ip]) {
           case '+': c->val++;break;
           case '-': c->val--;break;
           case '>': c=nxt(c);break;
           case '<': c=prv(c);break;
           case '.': putchar(c->val);break;
           case ',': c->val=getchar();break;
           case '[':
               if (c->val) break;
               ip++;
               t=1;
               while (t) {
                  t += pgm[ip] == '[';
                  t -= pgm[ip] == ']';
                  ip++;
               }
               ip--;
               break;
           case ']':
               if (!c->val) break;
               ip--;
               t=1;
               while (t) {
                  t -= pgm[ip] == '[';
                  t += pgm[ip] == ']';
                  ip--;
               }
               ip++;
               break;
       }
       ip++;
    }
    return 0;
}
#define YY \
" """;
#define XX /*
import sys;
ip=t=0
class Cell:
  pv=None
  nx=None
  val=0

  def prev(self):
     if not self.pv:
        self.pv = Cell()
        self.pv.nx = self
     return self.pv
  def next(self):
     if not self.nx:
        self.nx = Cell()
        self.nx.pv = self
     return self.nx

cell=Cell()
while ip<len(pgm):
  if pgm[ip]=='+': cell.val+=1;cell.val%=256
  elif pgm[ip]=='-': cell.val-=1;cell.val%=256
  elif pgm[ip]=='>': cell=cell.next()
  elif pgm[ip]=='<': cell=cell.prev()
  elif pgm[ip]=='.': sys.stdout.write(chr(cell.val))
  elif pgm[ip]==',':
      ch=sys.stdin.read(1)
      if ch:cell.val=ord(ch)
      else:cell.val=255
  elif pgm[ip]=='[' and not cell.val:
      t=1
      ip+=1
      while t:
        t += pgm[ip] == '['
        t -= pgm[ip] == ']'
        ip+=1
      ip-=1
  elif pgm[ip]==']' and cell.val:
      t=1
      ip-=1
      while t:
        t -= pgm[ip] == '['
        t += pgm[ip] == ']'
        ip-=1
      ip+=1
  ip+=1
#]*/

marinus

Posted 2014-02-24T01:01:21.657

Reputation: 30 224

I really like this answer. You managed to write a bf interpreter polyglot. But wouldn't bf running this get confused by the <> characters in things like #include<stdio.h>? – Kevin Kostlan – 2014-02-25T14:37:30.587

4@KevinKostlan: No, they're wrapped in braces, so they're skipped. (#define AA [) – marinus – 2014-02-25T18:12:43.750

2

Ruby and C

//; def void x; end; def main x, &b; b.call; end; def int x; end; arg = nil

//# Welcome to the Ruby/C polyglot thingy!
//# Simply insert whatever code you would like below.

void main(int arg) {

//; puts 1+1 # any Ruby code can be inserted on this line
//; puts 2+2 # the Ruby version is extendable to an arbitrary amount of lines
//; puts 3+3
//; puts 4+4

#define f printf(1+1) // any C code can be inserted on this line
//;f=nil
f;
#define g printf(2+2) // the C version is somewhat extendable
#define h printf(3+3)
#define i printf(4+4)
//;g=h=i=nil
g;h;i;

}

This takes advantage of the fact that

  • //# is a comment in both languages
  • //; is a comment in only C
  • "#define x " (with the space!) is (somewhat of) a comment in only Ruby
    • you then have to actually put it in the code, which is why I assign all the vars to nil and then simply place them in a new line

More extendable C version

//; def method_missing m, *args; end
#define a printf(1+1);
#define b printf(1+1);
#define c printf(1+1);
#define codegolf printf(1+1);
#define llama printf(1+1);
a b c codegolf llama

Doorknob

Posted 2014-02-24T01:01:21.657

Reputation: 68 138

0

PHP, ASP and JS:

WARNING: THIS WAS NOT TESTED:

Here is an attempt:

<!--<?error_reporting(0);?><% WebService Language="JScript" Class="MyClass" %>-->
<script runat="server">
console.log('/*<?=#*/$a='Math';/*?>*///#?>');
</script>

What should happen:

It should run the Javascript code on the server, when running on ASP.

In php, should output absolutely only the Javascript part, Saying 'Math' inside the whole comments.

In Javascript, it should put all that "garbage" in the console.

If it is invalid, just comment and I will remove this answer.

Ismael Miguel

Posted 2014-02-24T01:01:21.657

Reputation: 6 797