ULTIMATE CODEGOLF!!! (Codegolf a turing-complete system)

-4

The goal: write a program that implements a turing-complete system. It could be cellular automata, a tag system, a turing machine, an interpreter for a language of your own design... the type of system doesn't matter as long as it satisfies the following conditions:

  • Takes a "program" from the user as input (ex. the initial state of the turing machine)
  • Runs the program
  • Outputs the state of the system (or just the returns the output of the program)
  • It's possible to compute anything that can be computed with the right input program to your system.

Self-interpreting is forbidden.

As usual entries in the same language that implement the same type of system will be judged by byte count.

For example: programs which implement a universal turing machine in Python will be compared against other programs which implement universal turing machines in Python. The spirit of the challenge is basically the simplest possible programs that can model a turing-complete system.

Because of the diversity of possible programming languages, vote for entries that you believe are clever, elegant, or especially short. The winner will be the entry with the most votes.

J. Antonio Perez

Posted 2016-11-06T05:18:31.997

Reputation: 1 480

Question was closed 2016-11-06T06:52:32.157

1Would a single eval() be considered forbidden in this challenge? – Sunny Pun – 2016-11-06T05:20:44.943

Could you be more specific? – J. Antonio Perez – 2016-11-06T05:22:48.727

@JorgePerez Hmm.... I get the feeling people could just copy answers from the "Golf a BrainF**k Intepreter" thread... – Socratic Phoenix – 2016-11-06T05:29:47.413

What counts as a standard language? I suggest you implement a single scoring system across all languages rather than spend time deliberating between separate languages. Some languages will always out perform others regardless of the scoring system, that's why [tag:code-golf] challenges are generally not considered competitive between separate languages. – Post Rock Garf Hunter – 2016-11-06T05:31:30.470

@SocraticPhoenix While you could do this those answers would likely not be very competitive. There are other much simpler Turing complete systems that could be implemented to much better effect. This may be a dupe but I do not think it is a dupe of that question. – Post Rock Garf Hunter – 2016-11-06T05:34:18.737

I would also like to point out that some languages are made up of only "syntactic symbols". e.g. Brain-Flak

– Post Rock Garf Hunter – 2016-11-06T05:38:15.870

1I don't think the "word and symbol" system is good enough - it may cause ambiguities down the way. Just use byte-count, it should be fine. Also, what SunnyPun meant was a program (in Python, say) in which the code is eval(input()), and the input is valid Python code. That answer is valid under your current terms. – clismique – 2016-11-06T05:39:23.880

Also, you're judging this based on two criteria - which one is the one that determines the winner? – clismique – 2016-11-06T05:40:51.657

This is not [tag:kolmogorov-complexity]. That tag is reserved specifically for constant output programs as per the tag wiki. – Post Rock Garf Hunter – 2016-11-06T05:46:49.727

Uhhh... I just saw your "there's no specific winner" thing. The thing with PPCG is that there HAS to be a winner to every challenge - whether it's determined by byte-count, or votes. – clismique – 2016-11-06T05:49:48.257

Let us continue this discussion in chat.

– clismique – 2016-11-06T05:51:48.507

1Do X creatively popularity contests have fallen out of scope. In addition, asking to implement one choice out of the infinity of Turing complete languages makes this rather broad, and without an objective goal like code size, too broad. By the way, we have a sandbox where you can post challenge ideas and get feedback from the community before "going live". – Dennis – 2016-11-06T06:52:22.757

This is also a multi-dupe, in that answers to various earlier questions could be copied unmodified. Most of the questions in the [tag:interpreter] tag are about Turing-complete languages; cyclic tag springs to mind as a plausible provider of a winning answer to this question.

– Peter Taylor – 2016-11-06T06:57:16.760

If the answer below is acceptable then so are any of the answers to http://codegolf.stackexchange.com/questions/37014/interpret-pronounced-slashes

– Jerry Jeremiah – 2016-11-14T03:59:17.460

Answers

2

Python 3 for the language ///

A terribly long program, accepts input as a series of lines terminated by a newline and then the EOF character (May be Ctrl-Z or Ctrl-D depending on your OS).

s=''
try:
 while 1:
  s+=input()+'\n'
except:
 pass
try:
 while len(s):
  if'/'==s[0]:
   s=s[1:]
   f=r=''
   while'/'!=s[0]:
    if'\\'==s[0]:
     s=s[1:]
    f+=s[0]
    s=s[1:]
   s=s[1:]
   while'/'!=s[0]:
    if'\\'==s[0]:
     s=s[1:]
    r+=s[0]
    s=s[1:]
   s=s[1:]
   while f in s:
    s=s[:s.index(f)]+r+s[s.index(f)+len(f):]
  elif'\\'==s[0]:
   print(s[1])
   s=s[2:]
  else:
   print(s[0],end='')
   s=s[1:]
except:pass

Try it on Ideone!

It has been slightly golfed.

boboquack

Posted 2016-11-06T05:18:31.997

Reputation: 2 017

Could be golfed more by inlining multiple statements after a colon (e.g. while f in s:s=s[:s.index and elif'\\'==s[0]:print(s[1]);s=s[2:]). – wizzwizz4 – 2017-09-22T16:35:11.337

@wizzwizz4 I got your comment; unfortunately I'm not in a position where I can edit easily right now. – boboquack – 2017-09-22T19:54:59.470

That's fine. This is the (asynchronous) internet - I can wait! :-) – wizzwizz4 – 2017-09-22T21:06:01.217