创建最短图灵完全解释[关闭](Creating the shortest Turing-comple

我只是试图创造尽可能小的语言解释器。 你想加入和尝试？

游戏规则：

• 您应指定你解释编程语言。 如果它是你发明了一种语言，它应该与评论命令的列表。
• 您的代码应与示例程序，并分配给您的代码和数据变量的数据开始。
• 您的代码应与你的结果的输出端。 这是最好有在每一个步骤调试语句。
• 作为写你的代码应该是可运行的。
• 你可以假设数据是0和1（整型，字符串或布尔，你的选择）和输出是一个位。
• 语言应该是图灵完备的意义上，书面上的标准模型，比如图灵机，马尔可夫链，或类似您所选择的任何算法，这是相当明显（或解释）如何写后被executred程序通过你的解释执行的算法。
• 代码的长度被定义为代码的去除输入部分，输出部分，调试语句和非必要的空格后的长度。 请添加生成的代码和它的长度与职。
• 您不能使用功能，使编译器为您执行代码，如eval() ， exec()或类似的。

这是一个社区的Wiki，这意味着既没有问题，也没有答案，从票获得声望点数。 但无论如何投票！

Answer 1:

Python中，250个字节。

这个比伊利亚个n。Python的解决方案更长的时间，但语言是比较容易把握。 在这门语言的每个命令（我称之为Kaputt，对于德语单词“破”）是一个字节。 以下6个命令被定义：

• 0 ：推零到堆栈
• 1 ：推一到堆栈
• I ：（IF）弹出堆栈（必须是零或一）的值。 运行下面的代码块（直至“ i ”），如果它是一个; 跳过块，如果它是一个零。
• i ：（ENDIF）完if块和推如果块没有运行（因为“一I ”弹出一个零）。 请参阅下面为后者的解释。
• D ：（DEF）离开本层的待定义的函数的名称（见下文）并结合下面的块（直至“ d ”），以该名称。
• d ：（enddef）完的函数定义。
• 任何其他字节：检查是否有此功能（一个字节，但看到下面的编辑）的名称。 如果是这样，运行这个功能; 如果不是，按下此字节压入堆栈，通过直接使用D 。

嵌套IFS是合法的; 嵌套函数定义都没有。 这一事实i （ENDIF）推动一个当且仅当相应的块，如果未运行允许进行以下成语的类似的if / else / ENDIF结构：

# [code that left a one or zero on the stack]
I    # abbreviated "(" below
# [code to be run if it was a one]
0iI  # abbreviated "/" below
# [code to be run if it was a zero]
1iIi # abbreviated ")" below
# [continuing...]

请注意，注释，换行，空格等，实际上并没有允许。

下面是常见的函数举一些例子。 这些利用的缩写的( / )如上所述。

<D(/)d

定义函数< （POP）弹出从堆栈中的值，而无需使用它的任何东西。

&D((1/0)/<0)d

定义函数& （和），该弹出堆栈的两个值并按下一个，如果这两个值是那些，推送否则为0。

~D((11/10)/(01/00))d

定义函数~ （交换），该交换的堆栈顶部的两个值。

RD(R/<)d

定义函数R删除），该递归从栈中删除顶部的所有那些，然后删除两个值（最上面的一个的应该是零）。

下面解释函数期望程序P，它是一个字符串（或字节的任何其他可迭代），并且输入堆S，这是一个字节（可能是空的）列表。 解释器运行后，这个列表包含输出堆栈。

def i(p,S,F=0):
 A=S.append
 F=F or{}
 C=0
 k=[]
 for c in p:
  h=0in k
  if c=="d":C=0
  elif C!=0:C+=[c]
  elif c=="I":k+=[int(h or S.pop())]
  elif c=="i":k.pop()or A("1")
  elif 1-h:
   if c=="D":C=F[S.pop()]=[]
   else:i(F.get(c)or A(c)or"",S,F)

显然，没有任何闪失检查，所以i()预计，法律Kaputt代码。 测试用例：

script = "<D(/)d"                 # < = pop
script += "&D((1/0)/<0)d"         # & = and
script += "~D((11/10)/(01/00))d"  # ~ = swap
script += "RD(R/<)d"              # R = remove
script += "|D(<1/(1/0))d"         # | = or
script=script.replace("(","I")   
script=script.replace("/","0iI")
script=script.replace(")","1iIi") # ( and / and ) are no real commands of the language.

S=[]
i(script+"1111010111111111R",S)
assert S == ["1","1","1","1","0"]

S=[]
i(script+"00&",S)
assert S == ["0"]

S=[]
i(script+"01~",S)
assert S == ["1","0"]

S=[]
i(script+"00|",S)
assert S == ["0"]

S=[]
i(script+"01|",S)
assert S == ["1"]

快乐编码:-)

编辑：有什么，来强制令牌是只有一个字节解释所固有的。 需要，这是更用于与内置命令（这是一个字节，因为这使得解释器短）的一致性。 如果你传递一个字符串列表，而不是一个字符串，您可以编写更加易读Kaputt这样的代码：

script = """
inc D
    (
        (
            0 0
        /
            1 0
        )
    /
        1
    )
d
""".replace("(","I").replace("/","0 i I").replace(")","1 i I i").split()

这定义了一个函数inc该递增在堆栈的顶部的两个位的数字（LSB上顶部）。

测试：

for n in xrange(4):
    S=[]
    i(script + [str((n & 2)/2), str(n & 1), "inc"], S)
    assert S == [str(((n+1) & 2)/2), str((n+1) & 1)]

让我们把多字节函数名的语言扩展:-)

Answer 2:

这解释我刚刚创建了一个语言Python程序：

from random import randint
z = [randint(0,1), None]  # example: input data is 0 or 1
x = '_b_ed_a_i____d_ai'   # this program will set p = data[1] = not data[0]

# input x[i], data z[k]
# jumper j
# p is +1 or -1 each step
# commands:
#    a   set data = 0 or 1
#    b   j += 0 or +-9 depending on data
#    d   move data left or right
#    e   perform jump left or right
#    j   set jumper to 0
#    i   end program
# output: p or some data[x], both possible

g = globals()
p = i = 1
a = b = d = j = e = k = 0
while i:
    h = x[i]
    g[h] = p = -p
    i += 1 + j*e
    if a: z[k] = i % 2
    if z[k]: j += 9*b
    k += d
    g[h] = 0        
#    print(a, b, d, e, i, j, k, h, z)

print('Input:', z, 'Output:', p > 0)

优化的版本：

g=globals()
p=i=1
a=b=d=j=e=k=0
while i:
 h=x[i]
 g[h]=p=-p
 i+=1+j*e
 if a:z[k]=i%2
 if z[k]:j+=9*b
 k+=d
 g[h]=0

114个字节

更新：我想补充一点，我的程序的一点就是不要产生任何实际的语言，甚至不以某种方式有“最好的”（==“最短”）解释，而是表现出有趣的编程技巧。 例如，我依靠通过直接访问全局变量globals()所以我从来没有测试j命令，节省了宝贵的字节:)

Answer 3:

#include "/dev/tty"

Answer 4:

下面装配使用的代码A86得到一个150字节的BF解释！

    add dh,10h
    push dx
    add dh,10h
    push dx
    mov bl,80h
    lea dx,[bx+2]
    add bl,byte ptr [bx]
    mov byte ptr [bx+1],al
    mov ah,3dh
    int 21h
    pop ds,es
    jc l14
    mov bx,ax
    mov ah,3fh  
    mov cx,di
    xor dx,dx
    int 21h
    jc l14
    mov bx,ax
    xor ax,ax
    rep stosw
    xor di,di
    xor si,si
    inc ch
l1:
    cmp si,bx
    jae l14
    lodsb
    mov bp,8
    push l1
l2: 
    dec bp
    js ret
    cmp al,[bp+l15]
    jne l2
l3:
    mov cl,[bp+8+l15]
    jmp cx
l4:
    inc di  
    ret
l5:
    dec di
    ret
l6:
    es inc byte ptr [di]
    ret
l7:
    es dec byte ptr [di]
    ret
l8:
    mov ah,2
    es mov dl,[di]
    int 21h
    ret
l9:
    mov ah,8
    int 21h
    es mov [di],al
    ret
l10:
    es cmp byte ptr [di],dh
    jne ret
l11:    
    cmp si,bx
    jae l14
    lodsb
    cmp al,']'
    jne l11
    ret
l12:
    es cmp byte ptr [di],dh
    je ret
l13:    
    dec si
    jz l14
    cmp byte ptr [si-1],'['
    jne l13
l14:
    ret
l15:
    db '>'
    db '<'
    db '+'
    db '-'
    db '.'
    db ','
    db '['
    db ']'
    db offset l4-100h
    db offset l5-100h
    db offset l6-100h
    db offset l7-100h
    db offset l8-100h
    db offset l9-100h
    db offset l10-100h
    db offset l12-100h

指定命令行，不需要双引号的文件名，为BF源。

Answer 5:

不是我的，但看看210 位二进制演算自我解释这里 。

Answer 6:

用Perl编写的，140个字符长，包括外壳调用和标志：

perl -ne'push@a,split;if(eof){$i=0;while($i>=0){($a,$b,$c)=@a[$i..$i+2];$b>-1?$a[$b]-=$a[$a]:print chr$a[$a];$i=$b>-1&&$a[$b]<=0?$c:$i+3;}}'

可读的版本：

#!/usr/bin/perl -n
push @prog, split /\s+/, $_;
if(eof) {
  $i = 0;
  while($i >= 0) {
    ($a, $b, $c) = @prog[$i .. $i + 2];
    if($b > -1) {
      $prog[$b] -= $prog[$a];
    } else {
      print chr $prog[$a];
    }
    if($b > -1 and $prog[$b] <= 0) {
      $i = $c;
    } else {
      $i + 3;
    }
  }
}

以上是用于伪机器代码的解释程序的一个指令集计算机使用subleq指令。 基本上，源代码应该只是一串由空格分隔的数字。 一个简单的测试程序来验证我的结果（应打印“你好”和一个Unix换行符）：

0 0 6 72 105 10 3 -1 9 4 -1 12 5 -1 15 0 0 -1

测试输入的可读的版本（作品一样好）：

0    0     6
72   105   10
3   -1     9
4   -1     12
5   -1     15
0    0    -1

Answer 7:

我自己的条目，实现OISC的红宝石 。 这是85个字节长，我敢肯定，人们可以挤一些多用一些巧妙的技巧。 程序必须包含在代码数据（空间分隔的数字线）。 目前我无法提供工作写在OISC程序，但以后我会做到这一点。

p,m=0,gets.chomp.split.map(:to_i)
while p>0
p=(m[m[b]]-=m[m[a]])>0?p+3:c
end
$><<m[0]

该代码是相当简单的。 m是“记忆”包含程序和数据。 第一行初始化m与提供的代码，和p -存储器指针。 主循环subleq操作，与三元运算符写。 最后一行是包含在存储器输出数量聪明的办法。

Answer 8:

关于构建我以前的代码高尔夫入门 ，这里是（略概括为IO） OISC仿真器

FORTRAN77

Obsfucated和无负载的支撑架（655个字 ）：

  subroutine o(n,m)
  integer m(n)              
  l=1;                      
  do while (l.ne.0)
     i=m(l)
     j=m(l+1)
     k=m(l+2)
     mi=mg(n,m,i)
     mj=mg(n,m,j)
     if(j.eq.(n+2)) then
        write(6,*)mj-mi
     else
        m(l+1)=mj-mi
     endif
     if (m(l+1).lt.0) then
        l=mg(n,m,k)
     else
        l=l+3
     endif
  end do
  return
  end
  function mg(n,m,i)
  integer m(n)
  if (i.eq.n+2) then
     read(5,*)mg
  elseif (i.eq.n+1) then
     mg=0
  else
     mg=m(i)
  endif
  return
  end

与意见，装入支架等（2435个字符）：

      program c
      parameter (n=1024)        ! The size to use for memeory
      integer m(n)              ! represent the memory
c     Load a program into memory
      i=1
 1    read(5,*,end=2)l
c     write (6,*) "Load ",l," into location ",i
      m(i)=l
      i=i+1
      goto 1
c     Run the computer
 2    call o(n,m)
      stop
      end

      subroutine o(n,m)
c     Simulate a simple computer that supports only a single
c     instruction. Memory is a fixed size array of integers.
c
c     The supported instruction is subtract-branch-negative which we
c     give the assembly syntax
c
c     sbn i j k
c
c     and acts by subtracting the value in memeory location i from that
c     in location j and storing the result in j. If the result is
c     negative, the PC is set to k. Because there is only one opcode, it
c     is not represented, so a program consists simply of a series of
c     triplet (i,j,k), and the PC is generally incremented by 3. The
c     program counter starts at 1
c
c     Povisions for IO and halting are by way of special memory
c     location:
c
c     * PC=0 means halt
c     * writes (opcode argument j) to memory location n+1 send
c       output, reads from n+1 evaluate as 0
c     * reads (opcode argument i, j, k) from memory location n+2 fetch
c       input, writes to n+2 are forbidden
c     * All others reads and writes outside of memeory are forbidden

c     n                         ! the size of the computers memory 
      integer m(n)              ! an array representing the computers memory
      l=1;                      ! program counter
      do while (l.ne.0)
         i=m(l)
         j=m(l+1)
         k=m(l+2)
c        write (6,*) "Executing from PC=",l,": (",i,", ",j,", ", k,")"
c        handle the write special case for output
         mi=mg(n,m,i)
         mj=mg(n,m,j)
         if(j.eq.(n+1)) then
            write(6,*)mj-mi
         else
c           write (6,*) "Setting location ",j," to ",mj-mi
            m(l+1)=mj-mi
         endif
         if (m(l+1).lt.0) then
            l=mg(n,m,k)
         else
            l=l+3
         endif
      end do
      return
      end

c     Handle the various read special cases
      function mg(n,m,i)
      integer m(n)
      if (i.eq.n+2) then
         read(5,*)mg
      elseif (i.eq.n+1) then
         mg=0
      else
         mg=m(i)
      endif
c     write (6,*) "Read ",mg," from location ",i
      return
      end

样例程序：

13
1025
0

14 
1025
0

14
15
0

0
0
0

-1
1
0

导致输出：

$ cat trivial.oisc | ./a.out 
           1
          -1

这是符合市场预期。

这真的是非常简单的代码。 这里的关键是不是真的我怎么能紧紧代码，但如何简单，你需要为图灵完备的语言。

Answer 9:

106字节的解决方案被张贴到codegolf.com比赛。 它是用Perl编写并解释Brainfuck 。 有没有办法在这一点上进行审查，据我所知。

这不是我的解决方案，但我相信它比目前的项目短。 可能的解决方法应该是更短，因为没有必要使用Brainfuck作为图灵完备的语言。

Answer 10:

URM解释器的CoffeeScript ，143个字节 （167用新的行）。

这URM的版本已经由寄存器的无限量的，与零，继任者和经营者跳。 众所周知，这是图灵完备。

在URM程序被写入到阵列c （命令），并且输入是在阵列r寄存器）。 在计算之后的输出为r[0]并显示该值。

解释，以示例程序和输入，计算32 + 13（实际上输出45）：

# Addition program, similar to http://planetmath.org/examplesofunlimitedregistermachines
c = [['j', 1, 2, 4], ['s', 0], ['s', 2], ['j', 1, 1, 0]]

# Input: 32, 13, thus the desired output is: 45
r = [32, 13]

k = 0
while k < c.length
    t = c[k]
    k += 1
    if t[0] == 'z'
        r[t[1]] = 0
    if t[0] == 's'
        if !r[t[1]]?
            r[t[1]] = 0
        r[t[1]] += 1
    if t[0] == 'j' && r[t[1]] == r[t[2]]
        k = t[3]
alert r[0]

精缩版：

k=0
while k<c.length
 t=c[k]
 k+=1
 if t[0]=='z'
  r[t[1]]=0
 if t[0]=='s'
  if !r[t[1]]?
   r[t[1]]=0
  r[t[1]]+=1
 if t[0]=='j'&&r[t[1]]==r[t[2]]
  k=t[3]
alert r[0]

我真的在这段代码一样的是，实在是简单，容易理解。

Answer 11:

客户语言：SLA
关键词：
我 - 解读SLB q - 退出

自定义语言：SLB
关键词：
CP（“文本”） - 解读文本的C程序

例：
CP（ “＃包括\ NINT的main（）{看跌期权（\” 你好\ n \！ “）;返回0}”）

解释（SLA中的书面）： iq

3个字符！

文章来源: Creating the shortest Turing-complete interpreter [closed]