10
$\begingroup$

I recently watched a documentary where they talked about messages sent into space and how they imagined aliens figuring out how to understand them. They used math and geometry in clever ways.

I wonder if it may be possible to use programming to send such messages.

The question is then if it is possible to figure out the syntax and semantics of a language by looking at a program. I think a quine would be a natural choice of program since it is its own output regardless of what the symbols mean.

The following program is a quine written in X.

[ q < < [ q > { q } < ] ( q ) > > ] ( q )

All features of X are used in the program. X is Turing-equivalent.

The program is a quine according to definition at https://en.wikipedia.org/wiki/Quine_%28computing%29. It is not a "Cheating" quine.

There are no symbols in the language that are outputting themselves.

The challenge is to figure out the syntax and semantics of X.

The rules should be the minimal set of rules.

There should be a list of numbered rules, described in English. The rules should appear in the same order as the first example of a corresponding syntactic element in the program. Use x, y and z as wild-cards. x denoting the first item, y the next and then z.

For example:

  1. x < bite something less then x minutes ago

  2. { x } eject lab mouse named x

  3. x > y lets all eat x, y not

The winner is the one who has the most correct rules in the correct positions.

Answer

The point of this challenge was to test if it was in fact possible to become capable of reading a programming language by only looking at a quine for that language. I am very happy about how this turned out. Great success!

The accepted answer has all the key features right. There are subtleties that were not possible to decide based on the quine. Those would have been apparent with only a few additional examples.

Congratulations to The Dark Truth!

For completeness I have made an interpreter for the language with an included user manual: https://gist.github.com/thomasmf/031db24f0e63a3459e62

$\endgroup$
  • $\begingroup$ I'm a little confused here. Are you asking us to name the programming language, or describe the syntax and semantics? $\endgroup$ – Ian MacDonald Nov 17 '15 at 18:12
7
$\begingroup$

The program is written in a programming language that allows only single character variables and allows the compiling of strings into runnable code during compilation.

"running" a string means cutting it up into its logical units and returning the concatenated results of each logical unit.

Rules:

  1. [q ..... ] -> assign the string value "....." to the variable "q"
  2. <.....> -> run "....." and return the result / if "....." is no logical unit return it as string
  3. {q} -> return "q" as string
  4. (q) -> run "q" and print the result

when running the program the following happens (i will use "" to show strings and ++ for concatenation):

  1. [ q < < [ q > { q } < ] ( q ) > > ] ( q )
  2. [ q < < [ q > { q } < ] ( q ) > > ] -> assign the string "< < [ q > { q } < ] ( q ) > >" to q
  3. ( q ) -> run q and print resulting string
  4. < < [ q > { q } < ] ( q ) > >
  5. < [ q > ++ { q } ++ < ] ( q ) >
  6. "[ q" ++ "< < [ q > { q } < ] ( q ) > >" ++ "] ( q )"
  7. "[ q < < [ q > { q } < ] ( q ) > > ] ( q )" <- print this
$\endgroup$
  • $\begingroup$ Can you confirm that the programming language as you have it here is Turing equivalent? $\endgroup$ – Rob Watts Nov 17 '15 at 19:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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