Resumen:

Para cualquier idioma, ¿cuál es la menor cantidad de caracteres únicos para que su idioma sea Turing-Complete ?

Desafío:

Para cualquier idioma de su elección, encuentre el subconjunto más pequeño de caracteres que permita que su idioma sea Turing-Complete. Puede reutilizar su conjunto de caracteres tantas veces como desee.

Ejemplos:

• JavaScript: +!()[]( http://www.jsfuck.com )

• Brainfuck: +<>[](asume un tamaño de celda de envoltura)

• Python 2: ()+1cehrx(hecho de scripts como exec(chr(1+1+1)+chr(1)))

Puntuación:

Este desafío se puntúa en caracteres , no en bytes . Por ejemplo, las puntuaciones para los ejemplos son 6, 5 y 9.

Notas:

• Este desafío se diferencia de los demás en el sentido de que solo su idioma debe ser Turing-Complete (no necesariamente poder usar todas las características del idioma).

• Aunque puede hacerlo, no publique respuestas sin reducir los caracteres utilizados. Ejemplo: Brainfuck con 8 caracteres (ya que cada otro personaje es un comentario por defecto).

• DEBE proporcionar al menos una breve explicación de por qué su subconjunto es Turing-Complete.

Haskell, 4 caracteres

()=;

Con ()=podemos definir S, K e I. Las definiciones deben estar separadas por uno ;o un NL.

Definimos (==)como S (la segunda línea muestra una versión más legible):

((=====)==(======))(=======)=(=====)(=======)((======)(=======))
( a     == b      ) c       = a      c       ( b       c       )

(===) pedir:

(=====)===(======)=(=====)
 a     === b      = a

y (====)como yo:

(====)(=====)=(=====)
(====) a     = a 

Por suerte (==), (===), (====), etc, son los nombres de función / parámetros válidos.

Como señala @ ais523, SKI no es suficiente en un lenguaje fuertemente tipado como Haskell, por lo que debemos agregar un combinador de punto fijo (=====):

(=====)(======)=(======)((=====)(======))
(=====) f      = f      ((=====) f      )

JavaScript (ES6), 5 caracteres

Gracias a @ETHproductions y @ATaco por ayudar con esto; Este fue un proyecto grupal, y aunque la idea original era mía, muchos de los detalles son suyos. Vea la discusión de chat donde se desarrolló este subconjunto de JavaScript aquí .

[]+=`

Está bastante bien establecido que cualquier programa Javascript se puede escribir con los caracteres ([]()+! ), pero 5 caracteres no son suficientes . Sin embargo, este no es un desafío sobre escribir JavaScript arbitrario. Es un desafío escribir un lenguaje completo de Turing, y usar el hecho de que los idiomas completos de Turing no necesitan acceso al DOM, ni siquiera a las E / S interactivas, resulta que podemos escribir un programa con toda la funcionalidad requerida , incluso sin ninguna capacidad para ejecutar un evalo un equivalente.

Bootstrapping básico

JavaScript es muy flexible con los tipos. Entonces, por ejemplo, []es una matriz vacía, pero +[]es 0 y []+[]es la cadena nula. Notablemente, el hecho de que podemos producir 0 con este conjunto de caracteres hace posible simular el efecto de paréntesis para la agrupación; (a)se puede escribir como [a][+[]]. Podemos usar este tipo de truco para producir varios personajes usando solo +[]:

• [][+[]]es undefined(siendo el primer elemento de una matriz vacía); entonces
• []+[][+[]]es "undefined"(la cadena de undefined); entonces
• [[]+[][+[]]]es ["undefined"](envolviendo eso en una matriz); entonces
• [[]+[][+[]]][+[]]es "undefined"(su primer elemento); entonces
• [[]+[][+[]]][+[]][+[]]es "u"(su primera letra).

ues uno de los personajes más fáciles de crear, pero técnicas similares nos permiten crear una variedad de otros personajes. El mismo enlace que antes nos da la siguiente lista de caracteres accesibles con +[](esta es la misma lista que para +[](), excluyendo ,porque es la única construcción que usa paréntesis para un propósito que no sea la agrupación / precedencia):

0123456789acdefinotuvyIN (){}.

No podemos deletrear muchas palabras útiles de este conjunto de caracteres (recuerde que este es el conjunto de caracteres que podemos producir como cadenas ; no podemos ejecutarlas sin algún tipo de eval). Como tal, necesitamos otro personaje. Lo usaremos =porque será útil más tarde, pero por el momento lo usaremos para deletrear el operador de comparación ==. Eso nos permite producir falsey true, que se puede clasificar en cadenas e indexar, e inmediatamente nos permite agregar lrsa los caracteres que podemos incluir en las cadenas.

De lejos, la palabra más importante que esto nos permite deletrear, que no podíamos antes, es constructor. Ahora, JavaScript tiene una sintaxis de acceso a la propiedad que se ve así:

object.property

pero también puedes escribirlo así:

object["property"]

y nada nos impide usar una propiedad calculada, en lugar de una cadena literal. Así podemos hacer algo en la línea de

object["c"+"o"+"n"+"s"+"t"+"r"+"u"+"c"+"t"+"o"+"r"]

(con las letras generadas como se describe arriba; ¡el código rápidamente se hace muy largo!); eso es equivalente aobject.constructor , lo que nos permite acceder a los constructores de objetos arbitrarios.

Hay varios trucos que podemos hacer con esto. De lo mundano a lo fantástico:

• El constructor de un objeto es una función. En particular, tiene un nombre, y ese nombre es parte de la cadena de la función. Entonces, por ejemplo, podemos hacer [[]+[]][+[]]["constructor"]para llegar al constructor de una cadena, cuyo nombre es String, y luego stringificarlo para llegar a la capitalS carácter de . Esto expande nuestro alfabeto un poco, y vamos a necesitar algunos de los nuevos personajes más adelante.

• Todas las matrices tienen el mismo constructor; []["constructor"] == []["constructor"]es true(a diferencia de lo [] == []que es falso). Esto puede parecer menor, pero es muy importante, porque nos da un método para almacenar valores de forma persistente; podemos establecer una propiedad aleatoria en el constructor y leerla más tarde. (Esta es una de las razones por las que estamos usando =en particular, en lugar de una de las otras formas de generar truey false.) Por ejemplo, podemos evaluar [[]["constructor"]["a"]=[]]y luego leer[]["constructor"]["a"] y recuperar la misma matriz que almacenamos allí.

  Esto cumple uno de los requisitos que necesitamos para la integridad de Turing , la capacidad de almacenar y recuperar cantidades arbitrarias de datos. Podemos crear una celda de contras usando una matriz de dos elementos, tomando valores de nuestro almacenamiento de propiedades de constructor, y luego almacenarlo de nuevo en lugar de uno de esos valores, lo que nos permite construir estructuras de datos arbitrariamente grandes en la memoria; y podemos acceder a este almacenamiento haciendo lo contrario, derribándolo pieza por pieza hasta que los datos que queremos estén accesibles. La lectura es destructiva, pero eso es aceptable porque tenemos más de un lugar para almacenar datos, por lo que podemos copiarlos mientras los leemos y luego colocar la copia nuevamente en la ubicación original.

• Nos permite llegar al constructor para una función (hay muchas funciones a las que podemos acceder con nuestro alfabeto limitado; []["find"]es decir, Array.find, es la más accesible, pero hay otras). ¿Por qué es útil? Bueno, en realidad podemos usarlo para el propósito previsto de un constructor, ¡y construir funciones! Desafortunadamente, con nuestro conjunto de caracteres, no podemos pasar al constructor de la función una cadena calculada. Sin embargo, el uso de `sí nos permite pasarle un literal de cadena (por ejemplo []["find"]["constructor"]`function body goes here`); Esto significa que podemos definir valores personalizados de tipo de función con cualquier comportamiento cuando se ejecuta, siempre y cuando podamos expresar ese comportamiento completamente usando []+=. Por ejemplo, []["find"]["constructor"]`[]+[]`es una función bastante aburrida que calcula la cadena nula, la descarta y sale; eseLa función no es útil, pero las más complejas sí lo serán. Tenga en cuenta que aunque las funciones no pueden tomar parámetros o devolver valores, en la práctica no son problemas, ya que podemos usar el almacenamiento de propiedades del constructor para comunicarnos de una función a otra. Otra restricción es que no podemos usar` en el cuerpo de una función.

  Ahora, podemos definir funciones personalizadas, pero lo que nos detiene en este punto es la dificultad que tenemos para llamarlas . En el nivel superior del programa, podemos llamar a una función con`` , pero poder llamar funciones solo desde el nivel superior no nos permite hacer ningún tipo de bucle. Más bien, necesitamos funciones para poder llamarnos entre nosotros.

  Logramos esto con un truco bastante ingenioso. Recuerda la capitalS que generamos antes? Eso nos deja deletrear "toString". No lo vamos a llamar; podemos convertir cosas en cadenas agregándoles []. Más bien, lo vamos a reemplazar . Podemos usar el almacenamiento del constructor para definir matrices persistentes que se quedan. Luego podemos asignar nuestras funciones creadas a las matrices para llamar funciones, y por lo tanto nuestras funciones pueden llamarse entre sí, o por sí mismas. Esto nos da recurrencia, lo que nos da bucles, y de repente tenemos todo lo que necesitamos para completar Turing.toString métodos de , y esas asignaciones también se mantendrán. Ahora, todo lo que tenemos que hacer es un simple +[]en la matriz y, de repente, se ejecutará nuestra función personalizada. Esto significa que podemos usar los personajes+=[]

Aquí hay un resumen de un conjunto de características que le da integridad a Turing y cómo se implementan:

• Almacenamiento ilimitado : matrices anidadas en el almacenamiento del constructor
• Flujo de control : implementado usando ify recursividad:
  • if: convierte un booleano en un número e indexa en una matriz de 2 elementos; un elemento ejecuta la función para el thencaso cuando está en cadena, el otro elemento ejecuta la función para el elsecaso cuando está en cadena
  • Recursión : stringify un elemento apropiado del almacenamiento del constructor
• Secuencia de comandos : [a]+[b]+[c]evalúa a, by de cizquierda a derecha (al menos en el navegador que verifiqué)

Desafortunadamente, esto es poco práctico; no solo es enormemente grande dado que las cadenas deben construirse carácter por carácter a partir de los primeros principios, sino que tampoco tiene forma de hacer E / S (que no se requiere que sea Turing completo). Sin embargo, si termina, al menos es posible buscar manualmente en el almacenamiento del constructor, por lo que no es imposible depurar los programas y no son completamente no comunicativos.

Unario , 1 personaje

0

La elección del personaje realmente no importa; la duración del programa define el programa de brainfuck al que se transmite. Si bien la especificación exige 0caracteres, la mayoría de los transpiladores no parecen verificar esto.

vim, 9 8 7 6 caracteres

<C-v><esc>1@ad

Podemos construir y ejecutar un programa vimscript arbitrario de la siguiente manera:

1. Use la secuencia aa<C-v><C-v>1<esc>dd@1<esc>ddddpara obtener un <C-a>registro 1.

2. Ingrese al modo de inserción con a, luego inserte un a, que se usará para volver a ingresar al modo de inserción en una macro más adelante.

3. Para cada personaje en el programa vimscript deseado,

   1. use <C-v><C-v>1<esc>para insertar la secuencia literal <C-v>1,

   2. use @1(que es <C-a><cr>, en el que el final <cr>es un no operativo debido a estar en la última línea) tantas veces como sea necesario para incrementar el1 hasta que se alcance el valor ASCII del carácter deseado,

   3. y vuelva a ingresar al modo de inserción con a.

4. Elimine la línea (junto con una nueva línea final) en el 1registro con <esc>dd.

5. Ejecute el resultado como pulsaciones de teclas vim utilizando @1, luego, <esc>ddpara eliminar la línea ingresada por la nueva línea final del paso anterior.

6. Ejecute la secuencia arbitraria resultante de bytes con dd@1. Si comienza con a :, se interpretará como código vimscript y se ejecutará debido a la nueva línea final de dd.

No estoy convencido de que este sea un conjunto de caracteres mínimo, pero es bastante fácil demostrar que es Turing completo.

Perl, 5 personajes

<>^es

Al igual que con otros lenguajes de script, la idea es eval utilizar cadenas arbitrarias. Sin embargo, nuestro conjunto de caracteres no incluye comillas ni operadores de concatenación, por lo que construir cadenas arbitrarias será mucho más complejo. Tenga en cuenta que eval^"sería mucho más sencillo tratarlo, pero tiene un carácter más.

Nuestra herramienta principal es s<^><CODE>ee, que evalúa CODE, luego evalúa su salida. Máse puede agregar más, con el efecto esperado.

Obtenemos cadenas <>, que es el operador global excepto cuando no lo es. El primer carácter no puede ser <(de lo contrario, se parece al <<operador), los corchetes angulares deben estar equilibrados y debe haber al menos un carácter que no sea letra (de lo contrario, se interpreta como el operador de línea de lectura).

Al agrupar esas cadenas, podemos obtener cualquier combinación de caracteres ^B^V^S(*-/9;<>HJMOY[`\^begqstv, siempre que aceptemos tener algo de basura (los primeros tres son caracteres de control).

Por ejemplo, supongamos que queremos obtener "v99". Una forma de obtener v99es "><<" ^ "e>>" ^ "see" ^ "^^^", pero no podemos representar esas cadenas debido a las restricciones <>. Entonces, en su lugar, usamos:

<^<<^>><>>^<^^^^^<>>^<^^^^^^e>^<^^^^^^^>^<^^^^^e>^<^^^^e^>^<e^^es>^<^ee^^>^<^<^^^^^>>^<^<>^^^^>^<^^^^^^^e>^<^^^^^^^^>

Los rendimientos anteriores Y9;v99;, que, cuando se evalúan, producen el mismo resultado que un plano v99(es decir, el carácter con el código ASCII 99).

Por lo tanto, podemos usar todo el ^B^V^S(*-/9;<>HJMOY[`\^begqstvjuego de caracteres para generar nuestra cadena arbitraria, luego convertirla como se indica arriba y pegarla en a s<><CODE>eeeepara ejecutarla. Desafortunadamente, este juego de caracteres sigue siendo muy limitado, sin ninguna forma obvia de realizar la concatenación.

Pero afortunadamente, contiene la estrella. Esto nos permite escribir *b, que se evalúa en la cadena "*main::b". Entonces, *b^<^B[MMH^V^SY>(^ B, ^ V y ^ S son caracteres de control literales) nos da (6, $&);, que, cuando eval-ed otra vez, devuelve el valor de la variable partido de Perl, $&. Esto nos permite usar una forma limitada de concatenación: podemos anteponer repetidamente cosas para $_usar s<^><THINGS>e, y luego usar s<\H*><*b^<^B[MMH^V^SY>>eeepara evaluar $_( \Hcoincide con cualquier cosa que no sea un espacio en blanco horizontal; lo usamos en lugar del punto, que no está en nuestro juego de caracteres).

Usando 9-/, podemos generar fácilmente todos los dígitos. Usando dígitos vy concatenación, podemos generar caracteres arbitrarios (vXXX produce el carácter con el código ASCII XXX). Y podemos concatenarlos, para que podamos generar cadenas arbitrarias. Parece que podemos hacer cualquier cosa.

Escribamos un ejemplo completo. Supongamos que queremos un programa que imprima su propio PID. Comenzamos con el programa natural:

say$$

Lo convertimos a notación v:

s<><v115.v97.v121.v36.v36>ee

Reescribimos esto usando solo ^B^V^S(*-/9;<>HJMOY[`\^begqstv(el espacio en blanco es solo para legibilidad y no afecta la salida):

s<^><
    s<^><9*9-9-9-9-9-9>e;
    s<^><v>;
    s<v\H\H><*b^<^B[MMH^V^SY>>eee;
    s<^><9*9-9-9-9-9-9>e;
    s<^><v>;
    s<v\H\H><*b^<^B[MMH^V^SY>>eee;
    s<^><99-99/-9-99/-9>e;
    s<^><v>;
    s<v\H\H\H><*b^<^B[MMH^V^SY>>eee;
    s<^><99-9/9-9/9>e;
    s<^><v>;
    s<v\H\H><*b^<^B[MMH^V^SY>>eee;
    s<^><999/9-9/-9-9/-9-9/-9-9/-9>e;
    s<^><v>;
    s<v\H\H\H><*b^<^B[MMH^V^SY>>eee;
    s<\H*><*b^<^B[MMH^V^SY>>eee;
>eee;

Finalmente, convertimos el programa anterior a solo <>^es: pastebin . Lamentablemente, esto bloquea a Perl Excessively long <> operator, pero eso es solo una limitación técnica y no debe tenerse en cuenta.

Uf, ese fue todo el viaje. Sería realmente interesante ver a alguien crear un conjunto de 5 personajes que simplifique las cosas.

EDITAR: al usar un enfoque ligeramente diferente, podemos evitar alcanzar el límite de longitud <>. El intérprete de brainfuck completamente funcional solo usa <>^es: ¡ Pruébelo en línea! . Perl automatizado al <>^estranspilador: pastebin .

Python 2, 7 caracteres

exc="%\n

Cualquier programa de Python 2 puede codificarse con estos 7 caracteres ( \nes nueva línea).

Construyendo cadenas arbitrarias

Podemos realizar la concatenación aplicando repetidamente el operador de sustitución %en una sola cadena. Por ejemplo, si a=1, b=2, c=3, "%d%%d%%%%d" % a % b % cnos dará la cadena "123". Afortunadamente, las letras en execnos dan acceso a%x y %cque son básicamente hex()y chr(). Con %c, podemos construir cualquier cadena siempre que tengamos los números necesarios que representan los caracteres. Entonces podemos ejecutar esta cadena como código python usando la execpalabra clave.

Hacer números

Podemos acceder 0y1 desde el principio con comparaciones ( ==). Mediante una combinación de dígitos y módulo de concatenación, es posible construir el número 43que representa +en ASCII. Esto nos permite construir los números que necesitamos para nuestro código.

Poniendo todo junto

Omití varios detalles en esta explicación, ya que no son esenciales para comprender cómo se pueden escribir los programas bajo estas restricciones. A continuación hay un programa de Python 2 que escribí que convierte cualquier programa de Python en una versión funcionalmente equivalente que solo usa estos 7 caracteres. Las técnicas utilizadas están inspiradas en esta presentación sobre la anarquía del golf por k. También se utilizan algunos trucos simples para mantener el tamaño de los programas generados dentro de límites razonables.

import sys

var = {
    43: 'e',
    'prog': 'x', # the program will be stored in this variable
    'template': 'c',
    0: 'ee',
    1: 'ex',
    2: 'ec',
    4: 'xe',
    8: 'xx',
    16: 'xc',
    32: 'ce',
    64: 'cc',
    'data': 'cx', # source program will be encoded here
}

unpacker = 'exec"".join(chr(eval(c))for c in {}.split())'.format(var['data'])

source = sys.stdin.read()
charset = sorted(list(set(source+unpacker)))
codepoints = map(ord, charset)

output = (
    # create template for joining multiple characters
    '{}="%c%%c%%%%c%%%%%%%%c"\n'.format(var['template']) +

    # create 1
    '{0}={1}=={1}\n'.format(var[1], var['template']) +

    # create 0
    '{}={}==""\n'.format(var[0], var['template']) +

    # create 3
    # store it at var[43] temporarily
    (
        'exec"{0}=%x%%x"%{2}%{2}\n' +
        'exec"{0}%%%%%%%%=%x%%x%%%%x"%{1}%{2}%{1}\n'
    ).format(var[43], var[0], var[1]) +

    # create 4
    # this step overwrites the value stored at var[0]
    (
        'exec"{1}=%x%%x"%{0}%{1}\n' +
        'exec"{1}%%%%=%x%%x"%{2}%{0}\n'
    ).format(var[43], var[0], var[1]) +

    # create 43
    'exec"{0}=%x%%x"%{1}%{0}\n'.format(var[43], var[0])
)

# create powers of 2
for i in [2, 4, 8, 16, 32, 64]:
    output += 'exec"{0}={1}%c{1}"%{2}\n'.format(var[i], var[i/2], var[43])

for i, c in enumerate(codepoints):
    # skip if already aliased
    if c in var:
        continue

    # generate a new name for this variable
    var_name = ''
    if i < 27:
        for _ in range(3):
            var_name += 'exc'[i%3]
            i /= 3
    else:
        i -= 27
        for _ in range(4):
            var_name += 'exc'[i%3]
            i /= 3
    var[c] = var_name

    # decompose code point into powers of two
    rem = c
    pows = []
    while rem:
        pows.append(rem&-rem)
        rem -= rem&-rem

    # define this variable
    front = 'exec"{}={}'.format(var[c], var[pows.pop()])
    back = '"'
    for i, p in enumerate(pows):
        front += '%'*(2**i) + 'c' + var[p]
        back += '%' + var[43]
    output += front + back + '\n'

# initialise the unpacker
output += 'exec"""{}=""\n"""\n'.format(var['prog'])
i = 0
length = len(unpacker)
while i < length:
    if (length-i) % 4 == 0:
        # concat 4 characters at a time
        w, x, y, z = [var[ord(unpacker[i+j])] for j in range(4)]
        output += 'exec"{}%c={}%%{}%%{}%%{}%%{}"%{}\n'.format(var['prog'], 
                    var['template'], w, x, y, z, var[43])
        i += 4
    else:
        output += 'exec"""{}%c="%%c"%%{}"""%{}\n'.format(var['prog'],
                    var[ord(unpacker[i])], var[43])
        i += 1

# encode source data
output += var['data'] + '="""'
output += '\n'.join(var[ord(c)] for c in source)
output += '"""\n'

# execute the program
output += 'exec"exec%c{}"%{}'.format(var['prog'], var[32])

print output

Pruébalo en línea

Mathematica, 5 4 caracteres

I[]

es un carácter Unicode de uso privado , que actúa como un operador Functionque le permite escribir literales para funciones sin nombre con argumentos con nombre. El personaje se parece mucho ↦a Mathematica, así que lo usaré para el resto de esta respuesta para mayor claridad.

El uso de estos, podemos implementar el S, Ky Icombinadores de la lógica combinatoria:

I -> II↦II
K -> II↦III↦II
S -> II↦III↦IIII↦II[IIII][III[IIII]]

Un problema sintáctico con estos es que ↦tiene una precedencia muy baja, lo que será un problema si tratamos de pasar argumentos a estos combinadores. Normalmente lo arreglarías envolviendo un combinador Centre paréntesis (C), pero no tenemos paréntesis. Sin embargo, podemos usar Iy []envolver Calguna otra magia que tenga una precedencia lo suficientemente alta como para poder usarla más adelante:

I[C][[I[[]]I]]

Por último, para escribir una aplicación A x y z(donde Aes un combinador "parenthesised" como se muestra arriba, y x, y, zpueden o no ser parenthesised, o pueden ser expresiones más grandes), podemos escribir:

A[x][y][z]

Eso deja la pregunta de cómo funciona realmente el paréntesis equivalente. Trataré de explicarlo más o menos en el orden en que se me ocurrió.

Entonces, lo que tenemos sintácticamente para agrupar algo son los corchetes []. Los corchetes aparecen de dos maneras en Mathematica. Ya sea como invocaciones de funciones f[x]o como un operador de indexación f[[i]](que en realidad es solo una abreviatura Part[f, i]). En particular, esto significa que ni [C]tampoco [[C]]es una sintaxis válida. Necesitamos algo delante de eso. Eso, en teoría, puede ser cualquier cosa. Si usamos el Ique ya tenemos, podemos obtener, I[C]por ejemplo. Esto permanece sin evaluar, porqueI no es una función unaria (no es una función en absoluto).

Pero ahora necesitamos alguna forma de extraer Cnuevamente, porque de lo contrario no se evaluará realmente cuando intentemos pasar un argumentox .

Aquí es útil f[[i]]para las expresiones arbitrarias f, no solo para las listas. Asumiendo que fsí es de la forma head[val1,...,valn], entonces f[[0]]da head, f[[1]]da val1, f[[-1]]da , valnetc. Por lo tanto, necesitamos obtener cualquiera 1o -1extraer el Cnuevo, ya sea I[C][[1]]o I[C][[-1]]evalúa a C.

Nosotros podemos obtener 1a partir de un símbolo no definido como arbitraria x, pero para hacer eso, necesitaríamos otro personaje de la división ( x/xda 1para no definido x). La multiplicación es la única operación aritmética que podemos realizar sin caracteres adicionales (en principio), por lo que necesitamos un valor que se pueda multiplicar para dar -1o 1. Esto termina siendo la razón por la que elegí específicamente Inuestros identificadores. Porque Ipor sí mismo es el símbolo incorporado de Mathematica para la unidad imaginaria.

Pero que deja un último problema: ¿cómo en realidad se multiplica Ipor sí mismo? No podemos simplemente escribirII porque eso se analiza como un solo símbolo. Necesitamos separar estos tokens sin a) cambiar su valor yb) usar cualquier personaje nuevo.

El bit final de una magia es un comportamiento indocumentado: f[[]](o equivalente Part[f]) es una sintaxis válida y se devuelve f. Entonces, en lugar de multiplicar Ipor I, multiplicamos I[[]]por I. Insertar los corchetes hace que Mathematica busque un nuevo token luego y se I[[]]Ievalúa -1según sea necesario. Y así es como terminamos I[C][[I[[]]I]].

Tenga en cuenta que no podríamos tener uso I[]. Esta es una invocación sin argumentos de la función I, pero como dije antes Ino es una función, por lo que permanecerá sin evaluar.

Python 2, 8 caracteres

exc'%~-0

Estos caracteres permiten la traducción / ejecución de cualquier programa Python usando cadenas de formato y exec . Aunque no es necesario poder traducir ningún programa para completar Turing, estos son los pocos caracteres que conozco que lo hacen TC de todos modos. Que sea tan poderoso es solo una ventaja.

También se podría utilizar una comilla doble, así como cualquier dígito único además de cero. (Ahora que lo pienso, 1sin duda sería mejor, lo que resulta en programas más cortos, ya que es posible utilizar 1, 11y 111, también.)

Aquí está el programa print:

exec'%c%%c%%%%c%%%%%%%%c%%%%%%%%%%%%%%%%c'%-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~0%-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~0%-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~0%-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~0%-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~0

Pruébalo en línea

El programa base requiere

exec''

Cada personaje xagregado al programa requiere (char - count):

• % - 2**(n-1)
• c - 1
• - - ord(x)*2
• ~ - ord(x)*2
• 0 - 1

La excepción a esto es que se pueden tomar ciertas optimizaciones / atajos para acortar el programa codificado, como usar %'0'el carácter en 0lugar de 48 -~, etc.

Usos prácticos (también conocido como golf): utilicé esta táctica para resolver este desafío sin usar un personaje adicional para discapacitados.

Crédito por la lista de personajes y un programa codificador: aquí

Para obtener información sobre cómo encontrar un límite inferior en el tamaño del programa resultante (sin optimizaciones), consulte este comentario .

La cantidad de bytes necesarios aumenta O(2**n), por lo que este método no se recomienda para jugar al golf. Una quine que use esta restricción de fuente sería increíblemente larga.

C (no portable), 24 18 13 caracteres

aimn[]={};,1+

Esto cubre todos los programas del formulario.

main[]={<sequence of constants>};

... donde la secuencia de constantes (de la forma 1 + 1 + 1 ...) contiene la representación del código de máquina de su programa. Esto supone que su entorno permite que se ejecuten todos los segmentos de memoria (aparentemente cierto para tcc [¡gracias @Dennis!] Y algunas máquinas sin bit NX). De lo contrario, para Linux y OSX puede que tenga que anteponer la palabra clave consty para Windows puede que tenga que agregar una #pragmamarca explícitamente el segmento como ejecutable.

Como ejemplo, el siguiente programa escrito en el estilo anterior se imprime Hello, World!en Linux y OSX en x86 y x86_64.

main[]={111111111+111111111+11111111+11111111+1111111+1111111+1111111+1111111+1111111+11111+11111+11111+11111+11111+11111+11111+11111+111+11+11+11+11+11+11+1+1,1111111111+11111111+11111111+11111111+11111111+11111111+11111111+11111111+11111111+1111111+1111111+1111111+1111111+1111111+1111111+1111111+111111+11111+11111+11111+11111+11111+11111+1111+1111+1111+111+111+111+111+111+111,1111111111+111111111+111111111+111111111+111111111+111111111+111111111+11111111+11111111+11111111+11111111+11111111+11111111+11111111+11111111+1111111+1111111+111111+111111+111111+111111+11111+11111+11111+1111+1111+1111+1111+1111+1111+1111+1111+111+111+111+111+111+111+111+111+111+11+11+11+11+11+1+1+1+1+1+1+1,1111111111+111111111+111111111+111111111+111111111+111111111+111111111+11111111+11111111+11111111+11111111+11111111+11111111+11111111+11111111+1111111+111111+11111+11111+11111+11111+11111+11111+11111+11111+1111+1111+111+111+111+111+111+111+111+11+11+11+11+11+11+1+1+1+1,111111111+111111111+111111111+111111111+111111111+1111111+1111111+1111111+1111111+111111+111111+1111+1111+1111+1111+1111+1111+111+111+111+111+111+11+11+11+11+1+1+1+1,111111111+111111111+111111111+111111111+111111111+111111111+111111111+111111111+111111111+11111111+11111111+11111111+11111111+11111111+11111111+11111111+1111111+1111111+1111111+1111111+1111111+1111111+1111111+111111+111111+111111+111111+111111+111111+111111+1111+1111+1111+111+111+111+111+111+11+11+11+11+11+11+1+1+1+1+1+1,111111111+111111111+11111111+11111111+11111111+11111111+11111111+11111111+1111111+1111111+1111111+1111111+111111+111111+111111+111111+11111+11111+11111+11111+11111+11111+11111+11111+111+111+111+111+111+111+11+11+11+11+11+11+11+1,1111111111+111111111+111111111+111111111+11111111+11111111+11111111+11111111+1111111+1111111+1111111+111111+111111+111111+111111+111111+111111+111111+111111+11111+11111+11111+11111+11111+1111+1111+1111+1111+1111+1+1+1+1+1,1111111111+111111111+111111111+111111111+111111111+111111111+111111111+1111111+1111111+1111111+1111111+1111111+111111+111111+111111+11111+11111+11111+11111+1111+1111+111+111+111+111+111+111+111+111+111+11+11+11+11+11+1+1+1+1+1+1+1+1+1,1111111111+1111111111+111111111+111111111+111111111+111111111+111111111+111111111+11111111+11111111+11111111+11111111+11111111+11111111+1111111+1111111+111111+111111+111111+111111+11111+11111+1111+1111+1111+1111+1111+1111+1111+111+111+111+111+111+11+11+1+1+1+1+1,1111111111+111111111+111111111+111111111+111111111+111111111+111111111+111111111+111111111+111111111+11111111+11111111+11111111+11111111+1111111+1111111+1111111+1111111+111111+111111+111111+111111+111111+111111+111111+111111+11111+11111+11111+11111+1111+1111+1111+1111+1111+111+11+1+1+1+1+1,1111111111+1111111111+111111111+111111111+111111111+111111111+111111111+111111111+111111111+111111111+111111111+11111111+11111111+11111111+11111111+1111111+1111111+1111111+1111111+1111111+111111+111111+111111+11111+11111+11111+11111+11111+11111+11111+11111+11111+111+111+111+111+1+1+1+1+1+1+1,1111111111+1111111111+1111111111+111111111+111111111+111111111+111111111+111111111+111111111+111111111+111111111+11111111+11111111+11111111+11111111+11111111+11111111+1111111+1111111+1111111+1111111+1111111+111111+111111+111111+111111+11111+11111+1111+1111+111+111+111+111+111+111+111+111+111+11+11+11+11+11+11+1+1+1,1111111111+111111111+111111111+111111111+1111111+1111111+1111111+111111+111111+111111+111111+111111+111111+111111+1111+1111+1111+1111+1111+1111+1111+1111+111+111+111+111+111+111+111+111+111+1+1+1+1+1+1,111111+111111+11111+11111+11111+11111+11111+11111+11111+1111+1111+1111+1111+1111+1111+1111+1111+111+111+111+11+11+11+11+11+11+11+11+11+11,11111111+11111111+11111111+11111111+11111111+11111111+11111111+1111111+1111111+1111111+1111111+1111111+1111111+111111+111111+111111+11111+11111+11111+11111+11111+11111+11111+11111+1111+1111+111+111+111+111+111+111+11+11+11+11+11+11+11+1+1+1,111111111+111111111+111111111+111111111+111111111+111111111+111111111+11111111+11111111+11111111+11111111+1111111+1111111+1111111+1111111+1111111+111111+111111+111111+11111+11111+11111+11111+11111+11111+11111+11111+1111+1111+111+111+111+11+11+11+1,111111111+111111111+11111111+11111111+1111111+1111111+1111111+1111111+1111111+1111111+111111+111111+111111+111111+111111+11111+11111+11111+11111+11111+11111+11111+11111+11111+1111+1111+111+11+11+1+1+1+1+1,11111+11111+11111+11111+1111+1111+1111+1111+111+111+111+111+111+111+111+111+111+11+11+11+1+1+1+1+1};

Pruébalo en línea!

Retina , 6 caracteres.

$%`{¶

Además de avances de línea (0x0A).

Por un lado, estoy sorprendido de haber sido capaz de hacerlo tan bajo. Por otro lado, estoy muy descontento con la inclusión de %¶. Cada uno de ellos $`{se reutiliza para dos o incluso tres propósitos, pero en %¶ conjunto solo sirven para un propósito. Eso los hace parecer bastante derrochadores y destruye ligeramente la elegancia del enfoque. Espero que haya una manera de vencer esta construcción.

A la prueba. Voy a describir una manera simple de traducir sistemas de etiquetas cíclicas a Retina usando los caracteres anteriores.

Primero, usaremos `y {para el alfabeto binario en lugar de 0y 1. Estos son convenientes, ya que no necesitan escapar en una expresión regular, pero tienen significado para Retina o en sintaxis de sustitución. Estoy usando `for 0and {for 1, pero esta elección es arbitraria. Además, vamos a invertir la cadena (y las producciones) en la memoria, porque trabajar con el último personaje nos permite usar $y en $`lugar de ^y$' , maximizar la reutilización de caracteres.

Si la palabra inicial se denota por Sy ise llama a la producción th (invertida) , el programa resultante se verá así:pi

S
{`

{$
¶p1$%``
``$

{$
¶p2$%``
``$

{$
¶p3$%``
``$

...

Esta construcción inevitablemente crece en la memoria cada vez que se aplica una producción, y es poco probable que termine; de ​​hecho, en el punto donde el sistema de etiqueta cíclica terminaría (cuando la cadena de trabajo se vacía), el comportamiento del programa Retina resultante se vuelve básicamente indefinido

Veamos qué hace el programa:

S

Comenzamos inicializando la cadena de trabajo a la palabra inicial.

{`

Esto envuelve el resto del programa en un programa que se ejecuta hasta que no puede cambiar la cadena resultante (oye, ingenua detección de bucle infinito incorporada de forma gratuita ...). Los dos avances de línea no son realmente necesarios, pero separan el ciclo más claramente de las producciones individuales. El resto del programa pasa por cada una de las producciones y, debido al ciclo, las procesamos de manera cíclica una y otra vez.

Cada producción se procesa en dos etapas. Primero tratamos el caso de que el símbolo inicial (o en nuestro caso final) es {, en cuyo caso usamos la producción:

{$
¶pi$%``

La expresión regular solo coincide si la cadena termina en {. Si ese es el caso, lo reemplazamos con:

• Un salto de línea ( ¶). Solo trabajaremos con la última línea de la cadena de trabajo, por lo que esto descarta efectivamente la cadena de trabajo hasta ahora (por lo que el uso de memoria del programa crecerá y crecerá).
• La producción actual ( ), que estamos anteponiendo a la cadena de trabajo (donde el sistema de etiqueta cíclica lo agrega).pi
• La cadena de trabajo restante anterior ( $%`). Es por eso que necesitamos insertar el ¶: $%`recoge todo lo que queda del partido, pero solo en la misma línea. Por lo tanto, esto no ve toda la basura que nos queda de producciones anteriores. Este truco nos permite unir algo al final de la cadena de trabajo para insertar algo al comienzo de la cadena de trabajo, sin tener que usar algo como (.+)y$1 que explotaría significativamente la cantidad de caracteres que necesitamos.
• Un solo backtick ( `). Esto reemplaza efectivamente el {( 1símbolo) que emparejamos con un `( 0símbolo) para que la siguiente etapa no necesite saber si ya procesamos la producción actual o no.

La segunda parte de cada producción es el caso trivial donde se omite la producción:

``$

Simplemente eliminamos un final `. La razón por la que necesitamos dos `en la primera línea es que Retina considera que el primer backtick es el divisor entre la configuración y la expresión regular. Esto simplemente le da una configuración vacía para que podamos usar backticks en la propia expresión regular.

Java 7, 18 17 caracteres

\bcdefu0123456789

Todo el código fuente de Java se puede reducir a puntos de código Unicode. "a" no es necesario ya que solo se usa para *:jJzZ. El asterisco se usa para multiplicar o bloquear comentarios. La multiplicación es solo una suma repetida y puede usar comentarios de una sola línea (o simplemente omitirlos). Los dos puntos se usan para operadores ternarios, para los que puede usar una instrucción if y bucles foreach, que se pueden reemplazar por bucles normales. j y z no forman parte de ninguna palabra clave en java.

Intentar eliminar cualquier otro carácter requiere que agreguemos al menos uno de los caracteres requeridos en la placa de calderas de Java class a{public static void main(String[]a){}}. Vea abajo:

1 -> a (which has already been removed)
2 -> r (required for "String")
3 -> S (required for "String")
4 -> t (required for "static")
5 -> S (required for "String")
6 -> v (required for "void")
7 -> g (required for "String")
8 -> ( (required for "main(String[]a)"
9 -> i (required for "static")
b -> { (required for "class a{")
c -> l (required for "class")
d -> } (required for "(String[]a){}}")
e -> n (required for "main")
f -> o (required for "void")

Aquí hay un ejemplo con un programa Hello World ¡ Pruébelo en línea!

Java 8, 16 caracteres

\bdefu0123456789

Gracias a ais523 por señalar esto. Java 8 permite que las interfaces tengan métodos estáticos, lo que significa que podemos eliminar "c" porque no la necesitamos para la "l" en "clase". Se utiliza "c", por ,<lL\|lo que terminamos perdiendo un poco más de funcionalidad Java que cuando eliminamos "a", pero aún tenemos suficiente para completar. Pruébalo en línea!

Laberinto , 5 personajes

~{}

Saltos de línea más (0x0A) y espacios (0x20).

Voy a esbozar una prueba en forma de una reducción de Smallfuck (una variante reducida de Brainfuck que usa celdas de 1 bit). Tenga en cuenta que Smallfuck en sí no es completo de Turing porque el lenguaje especifica que su cinta debe ser finita, pero vamos a asumir una variante de Smallfuck con una cinta infinita, que luego sería completa de Turing (ya que Labyrinth no tiene memoria restricciones por diseño).

Una invariante importante a lo largo de esta reducción será que cada programa (o subprograma) dará como resultado un programa Labyrinth (o subprograma) que comienza y termina en la misma fila, y abarca un número par de columnas.

Labyrinth tiene dos pilas que se llenan inicialmente con una cantidad infinita (implícita) de 0s. {y }cambiar el valor superior entre estas pilas. Si consideramos que la parte superior de la pila principal es la "celda" actual, entonces estas dos pilas pueden verse como las dos mitades semi-infinitas de la cinta infinita utilizada por Smallfuck. Sin embargo, será más conveniente tener dos copias de cada valor de cinta en las pilas, para garantizar la invariante mencionada anteriormente. Por lo tanto <, y >será traducido a {{y }}, respectivamente (se puede cambiar si lo desea).

En lugar de permitir los valores de celda 0y 1, estamos usando 0y -1, que podemos alternar con ~(negación a nivel de bits). Los valores exactos no importan a los efectos de la integridad de Turing. Tenemos que cambiar ambas copias del valor en la pila, lo que nos da una traducción de longitud par nuevamente: se *convierte ~}~{.

Eso deja los comandos de control de flujo []. Labyrinth no tiene un flujo de control explícito, sino que el flujo de control está determinado por el diseño del código. Requerimos los espacios y los avances de línea para hacer ese diseño.

Primero, tenga en cuenta que ~~es un no-op, ya que los dos ~cancelan efectivamente. Podemos usar esto para tener rutas arbitrariamente largas en el código, siempre que su longitud sea uniforme. Ahora podemos usar la siguiente construcción para traducir AA[BB]CCa Labyrinth (estoy usando letras dobles para que el tamaño de cada fragmento en Labyrinth sea uniforme, como lo garantiza la invariante):

      ~~~~
      ~  ~~~
AA~~..~~~~ ~CC
   ~     ~
   ~     ~
   ~     ~
   ~~~BB~~

Aquí, ..hay un número adecuado de los ~cuales coincide con el ancho de BB.

Una vez más, tenga en cuenta que el ancho de la construcción sigue siendo uniforme.

Ahora podemos ver cómo funciona este ciclo. El código se ingresa a través de AA. El primero ~~no hace nada y nos permite llegar al cruce. Esto corresponde aproximadamente a [:

• Si el valor actual de la celda es cero, la IP continúa en línea recta, lo que finalmente se saltará BB. La ..parte sigue siendo un no-op. Luego llegamos a un single ~en otro cruce. Ahora sabemos que el valor actual no es cero, por lo que la IP toma el giro hacia el norte. Va alrededor de la curva en la parte superior, hasta que llega a otro cruce después de las seis ~. Entonces, en ese punto, el valor actual todavía no es cero y la IP toma el turno nuevamente para moverse hacia el este CC. Tenga en cuenta que los tres ~anteriores al CCretorno devuelven el valor actual 0, como debería ser cuando se saltó el bucle.
• Si el valor actual de la celda al comienzo del ciclo no es cero, la IP toma el giro hacia el sur. Corre seis más ~antes de llegar BB(que no hacen nada), y luego otros seis ~antes de llegar al siguiente cruce. Esto corresponde aproximadamente a la ].
  • Si la celda actual es cero, la IP sigue moviéndose hacia el norte. El siguiente ~hace que el valor no sea cero, de modo que la IP tome esta segunda unión, que combina la ruta con el caso de que el bucle se omitió por completo. Nuevamente, los tres ~devuelven el valor a cero antes de llegar CC.
  • Si la celda actual no es cero, la IP toma el giro hacia el oeste. Hay ~antes de la próxima unión, lo que significa que en este punto el valor actual es cero para que la IP siga yendo hacia el oeste. Luego habrá un número impar de ~antes de que la IP llegue nuevamente a la unión inicial, de modo que el valor se devuelva -1y la IP se mueva hacia el sur en la siguiente iteración.

Si el programa contiene algún bucle, entonces el primero AAdebe extenderse a la parte superior del programa para que la IP encuentre la celda correcta para comenzar:

~     ~~~~
~     ~  ~~~
AA~~..~~~~ ~CC
   ~     ~
   ~     ~
   ~     ~
   ~~~BB~~

Eso es eso. Tenga en cuenta que los programas resultantes de esta reducción nunca finalizarán, pero eso no es parte de los requisitos de la integridad de Turing (considere la Regla 101 o Fractran).

Finalmente, nos queda la pregunta de si esto es óptimo. En términos de caracteres de carga de trabajo, dudo que sea posible hacerlo mejor que tres comandos. Pude ver una construcción alternativa basada en máquinas Minsky con dos registros, pero eso requeriría =()o =-~, tener solo un comando de manipulación de pila pero luego dos comandos aritméticos. Me alegraría que me demuestren lo contrario en esto. :)

En cuanto a los comandos de diseño, creo que los avances de línea son necesarios, porque el flujo de control útil es imposible en una sola línea. Sin embargo, los espacios no son técnicamente necesarios. En teoría, podría ser posible crear una construcción que llene toda la cuadrícula con ~{}(o =()o =-~), o que utilice un diseño irregular donde las líneas no tengan la misma longitud. Sin embargo, escribir código como ese es increíblemente difícil, porque Labyrinth tratará cada celda como una unión y debe tener mucho cuidado para evitar que el código se bifurque cuando no lo desee. Si alguien puede probar o refutar si es posible omitir el espacio para la integridad de Turing, estaría encantado de dar una recompensa considerable por eso. :)

Haskell, 5 7 caracteres

()\->=;

Como lenguaje funcional, Haskell tiene lambdas, por lo que simular el cálculo lambda es fácil. La sintaxis para lambdas es que necesitamos al menos los caracteres . Además, necesitamos una cantidad ilimitada de símbolos variables para poder construir expresiones lambda arbitrarias. Por suerte, no necesitamos ningún nuevos caracteres para esto, porque , , , ..., son todos los nombres de variables válidos. De hecho, cada combinación de(\variable->body)argument()\->
(>)(>>)(>>>)\-> paréntesis internos es un nombre de variable válido, con la excepción de just \y ->, que están reservados para expresiones lambda, y --, que comienza un comentario de línea.

Ejemplos:

• S = (\(>)(\\)(-)->(>)(-)((\\)(-)))tipos a(t2 -> t -> t1) -> (t2 -> t) -> t2 -> t1
• K = (\(>)(-)->(>))tipos at -> t1 -> t
• Yo =(\(>)->(>)) tipos at -> t

Editar: Sin embargo, como ais523 ha señalado en los comentarios, esta construcción implementa cálculo lambda tipeado , que por sí solo no es completo de Turing porque carece de la capacidad de ingresar a bucles infinitos. Para solucionar esto, necesitamos alguna función que realice la recursividad. Hasta ahora utilizamos lambdas sin nombre, que no pueden llamarse a sí mismas porque, bueno, no tienen nombre. Entonces tenemos que agregar los caracteres =e ;implementar una fixfunción:

(>)=(\(-)->(-)((>)(-)));   -- equivalent to: f =(\ x -> x ( f  x ));

Con esta declaración, nuestro cálculo lambda se convierte en Turing completo, sin embargo, después de haber agregado =y ;, ya no necesitamos lambdas, como puede ver en la respuesta de nimi, que usa solo ()=;.

CJam, 3 personajes

Eliminado )según la sugerencia de Martin Ender

'(~

Similar a Python uno dado como ejemplo.

Usando '~puedes obtener el ~personaje. Luego (, usando , puede disminuirlo para obtener el carácter que desee ( ~es el último carácter ASCII imprimible). ~evalúa cualquier cadena como código CJam normal. Las cadenas se pueden construir obteniendo el carácter [(mediante decremento ~), evaluándolo, colocando una secuencia de otros caracteres y luego evaluando el carácter ]. A través de esto, puede compilar y ejecutar cualquier programa CJam usando solo estos tres caracteres.

Calculando 2 + 2 usando solo '(~

Brain-Flak , 6 personajes

(){}[]

Brain-Flak es un lenguaje minimalista con solo 8 caracteres disponibles. Sin embargo, se puede demostrar que existe un subconjunto de Brain-Flak que también se completa con solo 6 caracteres.

Lo primero que haremos es implementar una máquina Minsky con solo una pila de Brain-Flak. Si podemos demostrar que una máquina Minsky es posible con solo una pila, podemos demostrar que Brain-Flak está Turing completo sin el <>y []nilads. Esto no guardará ningún personaje de inmediato, pero lo hará en el futuro cuando demostremos que <...>no es necesario.

Una máquina Minsky es un tipo de autómata completo de Turing que tiene un número finito de registros ilimitados y dos instrucciones:

• Incremente el registro

• Si la disminución no es cero, haga la transición a una instrucción específica

Para configurar una estructura de goto en Brain-Flak podemos usar el siguiente fragmento:

(({}[()])[(())]()){(([({}{})]{}))}{}{(([({}{}(%s))]{}))}{}

Esto disminuirá el contador y correrá %s si es cero. Un grupo de estos encadenados juntos nos permitirá poner un número en la pila que indicará qué línea queremos pasar. Cada uno de estos disminuirá la parte superior de la pila, pero solo uno de ellos ejecutará el código.

Usamos esto como una envoltura para todas nuestras instrucciones de Minsky Machine.

Incrementar un registro particular es bastante fácil sin cambiar la pila. Se puede lograr con esta fórmula de cadena:

"({}<"*n+"({}())"+">)"*n

Por ejemplo, para incrementar el tercer registro, escribiríamos el siguiente código:

({}<({}<({}<({}())>)>)>)

Ahora solo tenemos que implementar la segunda operación. Verificar si un número es cero es bastante simple en Brain-Flak:

(({})){(<{}%s>)}{}

solo se ejecutará %ssi el TOS es cero. Así podemos hacer nuestra segunda operación.

Como las máquinas Minsky están completadas, Brain-Flak también está completa sin el uso de <>y[] operaciones.

Sin embargo, no hemos reducido el número de caracteres todavía porque <...>, y [...]todavía están en uso. Esto se puede remediar con una simple sustitución. Dado <...>que en realidad es equivalente a [(...)]{}en todos los casos. Por lo tanto, Brain-Flak se completa sin el uso de los caracteres <y >(más todas las no-ops)

> <> , 3 caracteres

> <> es factible en 3 con 1p-, que hacen:

1          Push 1
p          Pop y, x, c and put the char c in cell (x, y) of the codebox
-          Subtraction: pop y, x and push x-y

pproporciona reflexión, modificando el código fuente 2D colocando caracteres en el cuadro de código. Con 1-, puede insertar cualquier número en la pila ya que 1-resta uno y 111-1--(x-(1-1-1) = x+1 ) agrega uno.

Una vez que todos los 1p-comandos se han ejecutado, el puntero de la instrucción se ajusta y le permite ejecutar el código "real".

Un programa de ejemplo que calcula los números de Fibonacci (a partir de esta respuesta ) es:

111-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1--11-11-p111-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1--111-p111-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1--111-1--11-p111-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1--111-1-1--11-p111-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1--111-1-1-1--11-p111-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1--111-1-1-1-1--11-p111-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1--11-1p111-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1--11p111-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1--111-1--1p111-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1--111-1-1--1p111-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1--111-1-1-1--1p111-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1--111-1-1-1-1--1p111-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1--111-1-1-1-1-1--1p111-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1--111-1-1-1-1-1-1--1p111-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1--111-1-1-1-1-1-1-1--1p111-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1--111-1-1-1-1-1-1-1-1--1p111-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1--111-1-1-1-1-1-1-1-1-1--1p111-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1--111-1-1-1-1-1-1-1-1-1-1--1p111-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1--111-1-1-1-1-1-1-1-1-1-1-1--1p111-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1--111-1-1-1-1-1-1-1-1-1-1-1-1--1p111-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1--111-1-1-1-1-1-1-1-1-1-1-1-1-1--1p111-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1--111-1-1-1-1-1-1-1-1-1-1-1-1-1-1--1p

Pruébalo en línea! Una vez que todos los 1p-comandos se han ejecutado, el código se ve así:

01aa+v1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1- ...
@+&1->:?!;&:nao:

Salvo todo después vde la primera línea, este es un programa estándar de Fibonacci> <>.

bash, 9 caracteres

01456\$ '

Bash tiene una sintaxis $'\nnn'para ingresar caracteres con sus valores ascii octales. Podemos ingresar el evalcomando en este formato como $'\145\166\141\154'. Primero convertimos el resultado deseado en sus valores octales. Luego convertimos cualquier valor octal usando dígitos que no sean 0, 1, 4, 5 y 6 en expresiones que evalúen dichos valores octales usando $(())y restando, agregando un evalal frente. En nuestro paso final, agregamos otro evaly convertimos los paréntesis y el signo menos en sus valores octales. Usando este método podemos ejecutar cualquier comando bash, por lo que este subconjunto se está completando.

Ejemplo:

dc se convierte

$'\144\143' que se convierte

$'\145\166\141\154' \$\'\\144\\$((144-1))\' que se convierte

$'\145\166\141\154' $'\145\166\141\154' $'\$\\\'\\\\144\\\\$\050\050144\0551\051\051\\\''

Incidente , 2 personajes

Tampoco importa qué dos personajes elijas; cualquier combinación de dos octetos es completa de Turing en Incidente.

En realidad, demostrar esto es mucho más difícil de lo que cabría esperar, y al momento de escribir esto, la página de discusión en Esolang sobre Incidente está dedicada al problema. Sin embargo, intentaré dar un resumen de la prueba más simple conocida a continuación.

Antes de la prueba, algunos antecedentes. El incidente infiere las fichas utilizadas en el programa al mirar la fuente (una ficha es una cadena que aparece exactamente tres veces en la fuente, no es una subcadena de otra ficha y no se superpone con otra ficha potencial). Como tal, cualquier programa se puede convertir para usar casi cualquier conjunto de caracteres cambiando los tokens; el lenguaje es completo de Turing (¡y también es completo para E / S!), a pesar de ser increíblemente difícil de programar, por lo que "todo" lo que necesita es un método de codificación de tokens para que funcionen con solo dos caracteres.

Y ahora, aquí hay un resumen de la prueba (que fue encontrada por Ørjan, el matemático residente de Esolang). La idea es que codifiquemos un token usando dos copias de un personaje (digamos 1) en un gran mar del otro personaje (digamos 0). La distancia entre los 1s es diferente para cada token, pero siempre es un múltiplo de 4. Luego, para el relleno entre los tokens, usamos una lista adicional de 0s con un 1en el medio, pero el número de 0 en cada lado del 1es no un múltiplo de 4, sino un número exclusivo de esa incidencia particular del programa que no aparece en ninguna otra parte del programa. Eso significa que cada1 ...1dentro del relleno solo puede aparecer dos veces, por lo que no será parte de un token; cada token previsto contiene exactamente dos 1s, y ningún token falso puede contener más de uno 1. Luego, simplemente agregamos un poco de relleno a un lado para eliminar todos los tokens posibles que contengan una s agregando al menos cuatro copias de ellos.1 o cero1

Retina , 3 caracteres

{`

y nueva línea.

En primer lugar, necesitamos una nueva línea para poder hacer sustituciones (necesarias a menos que queramos ajustar todo el programa en una expresión regular, que necesitaría más caracteres); y `y {son la forma menos intensiva de caracteres para hacer bucles. Resulta que no necesitamos nada más.

Nuestro lenguaje de destino para implementar es una variante determinista de Thue (el no determinismo no es necesario para la integridad de Turing; es posible escribir un programa Thue para que funcione correctamente independientemente del orden de evaluación utilizado). La idea básica es compilar pattern::=replacementen

`pattern
replacement

(que es una traducción directa de Retina de Thue; alternativamente, si conoce Retina pero no Thue, puede usarla como un método para aprender cómo funciona Thue); como excepción, el primer patrón está precedido por el {`lugar (para colocar todo el programa en un bucle; los programas continúan ejecutándose hasta que no sea posible realizar más sustituciones, y esto hace que la Retina funcione de la misma manera).

Por supuesto, esto significa que tenemos que demostrar que Thue Turing está completo con solo {y `en los patrones y el reemplazo, pero eso es bastante simple; reemplazamos un carácter con código ascii n con `, n +1 {y otro `. Es claramente imposible que un patrón coincida en cualquier lugar excepto en los límites de los personajes, por lo que esto terminará haciendo lo mismo que el programa original.

Brachylog , 5 caracteres

~×₁↰|

Este subconjunto de caracteres nos permite implementar una versión de Fractran en la que los únicos números que pueden aparecer son productos de repunidades (es decir, productos de números que pueden escribirse en decimal usando solo el dígito 1). ~×(con un entero como subíndice) divide el valor actual por ese entero, pero solo si se divide exactamente (de lo contrario, "falla" y busca que se ejecute otro caso; |separa los casos). ×multipliquemos por un entero. Entonces, usando ~×₁|podemos implementar un paso de una ejecución de Fractran. Luego ↰nos permite recurrir, ejecutando todo el programa nuevamente en el nuevo valor actual. Aquí hay un ejemplo de un programa Fractran ( 11111111111111111111111/111) muy simple traducido a Brachylog.

Entonces, ¿está completo este Turing? Todo lo que necesitamos para completar Fractran Turing es una cantidad suficientemente grande de números primos (suficiente para escribir un intérprete para un lenguaje completo de Turing en el propio Fractran). Hay cinco probados y cuatro sospechosos.repunite los primos, además de, muy posiblemente, los que aún no se han descubierto. En realidad, eso es más de lo que necesitamos en este caso. El programa verifica las posibilidades de izquierda a derecha, por lo que podemos usar un primo como puntero de instrucción, y dos más como contadores, demostrando la integridad de Turing con solo tres primos (algo bueno también, porque nos permite usar las repunidades con 2, 19 y 23 dígitos, sin tener que recurrir a las repeticiones probadas pero molestamente grandes con 317 o 1031 dígitos, lo que haría que el código fuente sea bastante difícil de escribir). Eso hace posible implementar una máquina Minsky con dos contadores (suficiente para completar Turing).

Así es como funciona la compilación específicamente. Usaremos los siguientes dos comandos para la implementación de nuestra máquina Minsky (esto se conoce como Turing completo), y cada comando tendrá un número entero como etiqueta:

• Etiqueta L: Si el contador {A o B} es cero, pase a X. De lo contrario, disminuya y pase a Y.
• Etiqueta L: Incrementa el contador {A o B}, luego pasa a Z.

Elegimos qué comando ejecutar mediante la colocación de potencias de 11 en el denominador, las potencias más altas primero; el exponente de 11 es la etiqueta del comando. De esa manera, la primera fracción que coincida será el comando que se está ejecutando actualmente (porque los anteriores no se pueden dividir entre todos esos 11). En el caso de un comando de decremento, también colocamos un factor de 1111111111111111111 o 11111111111111111111111 en el denominador, para el contador A o B respectivamente, y seguimos con otro comando sin ese factor; el primer comando implementará el caso de "decremento" y el segundo el caso de "cero". Mientras tanto, el "goto" será manejado por una potencia apropiada de 11 en el numerador, y el "incremento" por un factor de 1111111111111111111 o 11111111111111111111111 en el numerador.

Befunge-98, 3 personajes

Hasta donde sé, se supone que Befunge-98 debe estar completo, por lo que solo tenemos que mostrar cómo se puede generar cualquier programa Befunge-98 utilizando solo tres caracteres. Mi solución inicial se basó en los siguientes cuatro caracteres:

01+p

Podemos obtener cualquier número entero positivo en la pila agregando múltiples 1valores junto con el +comando, y para cero simplemente usamos 0. Una vez que tenemos la capacidad de presionar cualquier número que queramos, podemos usar elp comando (poner) para escribir cualquier valor ASCII en cualquier ubicación en el campo de juego Befunge.

Sin embargo, como señaló Sp3000 , en realidad puedes sobrevivir con solo los tres caracteres:

1-p

Cualquier número negativo puede calcularse comenzando con 1y luego restando repetidamente 1(por ejemplo, -3 sería 11-1-1-1-). Entonces, cualquier número positivo se puede representar restando 1-n de 1, donde 1-n es un número negativo que ya sabemos cómo manejar (por ejemplo, 4 = 1 - (- 3), que sería111-1-1-1-- ).

De este modo, podemos usar nuestros tres caracteres para escribir una especie de gestor de arranque que genera lentamente el código real que queremos ejecutar. Una vez que este cargador termine de ejecutarse, se ajustará al inicio de la primera línea del campo de juego, que en ese momento debería contener el inicio de nuestro código recién generado.

Como ejemplo, aquí hay un gestor de arranque que genera el código Befunge necesario para sumar 2 + 2 y generar el resultado: 22+.@

Y para un ejemplo un poco más complicado, este es "Hello World": "!dlroW olleH"bk,@

Ruby, 8 caracteres

eval"<1+

Inspirado por las respuestas de Python

Cómo funciona

• eval puede usarse para ejecutar una cadena arbitraria.
• "<1+ es el conjunto mínimo de caracteres necesarios para construir cualquier cadena

Se puede construir una cadena en rubí usando la cadena vacía como punto de partida y añadiéndole caracteres ascii, por ejemplo:

eval ""<<111+1<<11+11+11+1<<111<<11+11+11+1

en realidad es equivalente a

eval ""<<112<<34<<111<<34

que evalúa la cadena

p"o"

OCaml, 9 caracteres

fun->()`X

Estos caracteres son suficientes para implementar el cálculo del combinador de SKI en OCaml. Cabe destacar que podemos evitar el uso del espacio con paréntesis suficientes. Desafortunadamente, las expresiones lambda en OCaml requieren la funpalabra clave, por lo que no es posible una solución más concisa. Sin embargo, se pueden usar las mismas letras para construir nombres de variables arbitrarias si se desean expresiones lambda más complejas.

S combinador:

fun(f)(u)(n)->f(n)(u(n)) con tipo ('a -> 'b -> 'c) -> ('a -> 'b) -> 'a -> 'c

K Combinador:

fun(f)(u)->u con tipo 'a -> 'b -> 'b

I combinador:

fun(f)->f con tipo 'a -> 'a

Como se señaló en ais523, es insuficiente codificar simplemente SKI. Aquí hay una codificación para Z usando variantes polimórficas para manipular el sistema de tipos. Con esto, mi subconjunto debería estar completo.

Combinador Z:

fun(f)->(fun(`X(x))->(x)(`X(x)))(`X(fun(`X(x))y->f(x(`X(x)))y))

con tipo (('a -> 'b) -> 'a -> 'b) -> 'a -> 'b

Lenguajes concatenativos basados ​​en pila, 4 caracteres

Baja carga

():^

GolfScript

{}.~

CJam

{}_~

GS2

• retroceso, tabulación, @espacio (sabía que GS2 usaba muchas veces las no imprimibles, pero esto es ridículo ...)

dc (sugerido por @seshoumara)

[]dx

La subcarga ha sido probada con Turing completo solo con el uso de ():^(gracias al matemático residente de Esolang Ørjan). La prueba es demasiado larga para explicarla aquí, pero si está interesado, puede leerla aquí. .

Los comandos en cuestión son ()(colocar código literal en la pila), :(elemento de pila superior duplicado) y ^(evaluar la parte superior de la pila). Estos comandos son bastante comunes en los lenguajes basados ​​en pila (especialmente los lenguajes concatenativos), por lo que he dado una colección de ellos anteriormente; Todos estos idiomas están completos en Turing en 4 caracteres por la misma razón que Underload.

Espacio en blanco, 3 caracteres

STL

Ses espacio, Tes tabulador y Les nueva línea.

Raqueta (esquema), 4 caracteres

(λ)

Usando solo λ, paréntesis y espacio, podemos programar directamente en el subconjunto Lambda Calculus de Scheme. Reutilizamos el carácter λ para todos los identificadores al concatenarlos juntos para proporcionar un número arbitrariamente grande de identificadores únicos.

Como ejemplo, aquí está el clásico combinador Omega, que se repite para siempre.

((λ (λλ) (λλ λλ)) (λ (λλ) (λλ λλ)))

Python 3, 9 caracteres

exc('%1+)

Ver mi respuesta de Python 2 de para una explicación básica. Esta respuesta se basa en esa.

En lugar de simplemente usar los mismos caracteres que Python dos con la adición de (), podemos soltar un carácter ya que ahora tenemos el uso de paréntesis. Los programas seguirán teniendo la forma básica de

exec('%c'%stuff)

pero acortamos la duración del programa usando en +lugar de -, y luego podemos eliminar ~usando en 1lugar de 0. Luego podemos agregar 1, 11y 111obtener los valores ASCII requeridos.

El programa se print()convierte en el siguiente en su forma más corta:

exec('%c%%c%%%%c%%%%%%%%c%%%%%%%%%%%%%%%%c%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%c%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%c'%(111+1)%(111+1+1+1)%(11+11+11+11+11+11+11+11+11+1+1+1+1+1+1)%(11+11+11+11+11+11+11+11+11+11)%(111+1+1+1+1+1)%'('%')')

Pruébalo en línea

Puede estar pensando para sí mismo, ¿cómo se puede crear un byte NUL sin él 0? ¡No temas, joven saltamontes! porque tenemos la capacidad de usar también %para matemáticas, creando cero con 1%1.

PHP 7, 6 caracteres

'().;^

La idea es que es posible ejecutar código arbitrario utilizando la siguiente construcción:

('create_function')('','<code>')();

eval no funcionaría aquí, porque es una construcción de lenguaje y no se puede llamar usando funciones variables.

create_function y el código podría escribirse como una concatenación de XOR bit a bit de caracteres disponibles:

(<char1_1>^<char1_2>^...).(<char2_1>^<char2_2>^...)...

Usando ().;^para <charX_Y>, podemos obtener

()./:;<=JKLMXY^_bcdepqvw

y algunos caracteres no imprimibles. No es suficiente, pero ahora también podemos llamar 'eXp'()y obtener algunos caracteres numéricos:

''.'eXp'('eXp'('')) -> 1
''.'eXp'('eXp'('eXp'(''))) -> 2.718281828459
''.'eXp'('eXp'('eXp'('eXp'('eXp'(''))))) -> 3814279.1047602

Nos da 1, 2y 3(otros caracteres serán ignorados por XOR, si la otra cadena tiene un carácter de largo). Desde ().;^123ahora podemos generar todo el conjunto de caracteres ASCII.

Pruébalo en línea

Pyke, 5 personajes

0h.CE

Esto es capaz de producir un número infinitamente grande, convertirlo en una cadena y luego evaluarlo como código Pyke.

Explicación del código:

0- Agregue 0 a la pila. Esto es necesario para comenzar un número

h- Incremente el número antes. Al repetir esto una cantidad arbitraria de veces, puede crear números que son infinitamente grandes. Pyke admite bignums tal como está escrito en Python, que los usa de forma predeterminada.

.C- Convierta un número en una cadena usando el siguiente algoritmo: ( enlace Github )

def to_string(num):
    string = ""
    while num > 256:
        num, new = divmod(num, 256)
        string = chr(new) + string
    string = chr(num) + string
    return string

En este punto, podemos crear una cantidad arbitraria de cadenas y números naturales en Pyke con valores arbitrarios. Se pueden crear números en la forma correspondiente a la expresión regular 0(h)*y se pueden crear cadenas con 0(h)*.C. Se pueden entrelazar entre sí para crear una mezcla arbitraria de cadenas y enteros.

E- evaluar una cadena como código Pyke. Esto usa el mismo entorno que el código Pyke que ya se está ejecutando, por lo que compartirá cosas como la entrada.

Intento de prueba de que Pyke está Turing completo.

Una de las formas más simples de mostrar un idioma es completarlo implementando Brainf * ck en él. Esto es probablemente mucho más difícil en Pyke que en muchos otros idiomas porque sus operaciones de lista y diccionario son prácticamente inexistentes debido a la falta de necesidad en el área en la que Pyke está diseñado para ejecutarse: code-golf .

Primero creamos un intérprete para brainf * ck y lo codificamos utilizando nuestro algoritmo anterior para crear un número y luego expresar ese número con 0y h. Luego creamos la cadena que contiene el código que se ejecutará exactamente de la misma manera. Si lo dejáramos así, tendríamos la pila como

string containing brainf*ck code
string containing brainf*ck interpreter

Esto significa que el código tiene que estar en la forma opuesta ya que la pila Pyke es la primera en entrar y la última en salir.

Ahora para la parte divertida: ¡el intérprete brainf * ck con la friolera de 216 bytes!

Q~B"><ht.,".:=B;Z]1=L;W~Bo@D=c"ht"{I~c~LZ@EZ]1~LR3:=L)~c\,qIz.oZ]1~LR3:=L)~c\[email protected])~c"<>"{I~c"<>""th".:ZE=ZZ1_qI0=Z~L0"":0]10:=L)Z~LlqI~L~Ll"":1_]10:=L))~c\[qI~LZ@0qI\]~B~o>@~o+h=o))~c\]qI~o\[~B~o<_@-t=o)~o~BlN

Pruébalo aquí!

Si desea probar el código en forma semi-completa pero editable, ¡ pruébelo aquí!

Para convertir una cadena en un número, puede usar el siguiente código de Python:

def conv(string, t=0):
    t *= 256
    t += ord(string[0])
    if len(string) != 1:
        return conv(string[1:], t)
    return t

¡La (casi) solución final se puede probar aquí!

Explicación del intérprete Brainf * ck

Primero separemos el programa en partes:

• La inicialización:

​

Q~B"><ht.,".:=B;Z]1=L; - The initialisation part
Q~B"><ht.,".:          - input.replace("><+-.,[]", "><ht.,")
                       - replace the characters in brainf*ck with some modified ones. 
                       - this means we can `eval` the add and subtract bits easily.
             =B;       - set `B` to this.
                       - The `B` variable contains the instructions
                Z]1=L; - set `L` to [0]
                       - `L` contains the stack, initialised with 0

• El bucle principal:

​​ ​ ​

W~Bo@D=c !code! ~o~BlN - The main loop
W                      - do
 ~Bo@D=c               -  c=B[o++]
                       -  the c variable is used to store the current character.
                ~o~BlN - while
                ~o     -   o 
                     N -  ^ != V 
                  ~Bl  -   len(B)
                       -  this stops the program running once it's finished.

• Las instrucciones
  • De incremento / reducción:+-

​​ ​ ​

"ht"{I~c~LZ@EZ]1~LR3:=L) - The bit that does incrementing and decrementing
"ht"{I                 ) - if c in "ht"
        ~LZ@             -  L[Z]
                         -  `Z` contains the current stack pointer
      ~c    E            -  eval current character with ^ as an argument
                         -  returns the contents of `Z` either incremented or decremented
             Z]1~LR3:=L  - L[Z] = ^

• Entrada ,:

​​ ​ ​

~c\,qIz.oZ]1~LR3:=L) - The code for output 
~c\,qI             ) -  if character == ",":
      z.o            -    ord(input)
         Z]1~LR3:=L  -   L[Z] = ^

• Salida .:

​​ ​ ​

~c\[email protected]) - The code for input 
~c\.qI        ) - if c == ".":
      ~LZ@      -    L[Z]
          .C    -   chr(^)
            pK  -  print(^)

• Desplazar a la izquierda / derecha <>:

​​ ​ ​

~c"<>"{I~c"<>""th".:ZE=Z - main part 
~c"<>"{I                 - if "<>" in c:
        ~c"<>""th".:     -  c.replace("<>", "th")
                    ZE=Z -  Z = eval(char, Z)

Z1_qI0=Z~L0"":0]10:=L) - lower bound check
Z1_qI                ) - if Z == -1:
     0=Z               -  Z = 0
        ~L0"":         -  L.insert("", 0)
              0]10:=L  -  L[0] = 0

Z~LlqI~L~Ll"":1_]10:=L) - upper bound check
Z~LlqI                ) - if Z == len(L):
        ~Ll"":          -  L.insert("", len(L))
      ~L      1_]10:=L  -  L[-1] = 0

• Los condicionales [:

​​ ​ ​

~c\[qI~LZ@0qI\]~B~o>@~o+h=o)) - Code for `[`
~c\[qI                      ) - if c == "[":
      ~LZ@0qI              )  -  if L[Z] == 0:
               ~B~o>          -     B[o:]
             \]     @         -    ^.find("]")
                     ~o+h=o   -   o = o + ^ + 1

- Y ]:

​​ ​ ​

~c\]qI~o\[~B~o<_@-t=o) - Code for `]`
~c\]qI               ) - if c == "]":
          ~B~o<_       -    reversed(B[:o])
        \[      @      -   ^.find("[")
      ~o         -t=o  -  o = o - ^ -1

Apilado, 5 caracteres

{!n:}

Esto es sorprendentemente corto. Si Stacked puede implementar cada una de las combinaciones de SKI, entonces es Turing Complete. Resumen:

• I combinador - la función de identidad. x -> x
• K combinador - la función constante. x -> y -> x
• S combinador - la función de sustitución. (x, y, z) -> x(z)(y(z))

Yo combinador: {!n}

Ahora, para los detalles apilados. {! ... }es una n-lambda Es una función unaria cuyo argumento es implícitamente n. Luego, la última expresión se devuelve desde la función. Por lo tanto, {!n}es una función que toma un argumento ny producen .

K combinador: {!{:n}}

Ahora, {:...}es una función que no toma argumentos y regresa .... Combinando esto con nuestra formación n-lambda, obtenemos (agregando espacios en blanco para mayor claridad):

{! { : n } }
{!         }   n-lambda. arguments: (n)
   { : n }     lambda.   arguments: ()
       n       yields n.

S combinador: {n!nn!nnn:nnn{!n}!nn!nnn{!n}!n!!}

Ok, esto parece un poco más complicado. Entonces, una lambda toma argumentos, separados por caracteres no identificadores. Por lo tanto, la lambda en el encabezado es equivalente a:

{n nn nnn:nnn{!n}!nn!nnn{!n}!n!!}

Este es un lambda que tiene tres argumentos, n, nn, y nnn. Vamos a sustituir estos con x, yy zpara mayor claridad:

{x y z:z{!n}!y!z{!n}!x!!}

Los dos {!n}!son solo una función de identidad para evitar nuevamente los espacios en blanco, donde !significa "ejecutar". Entonces, nuevamente, reduciendo:

{x y z:z y!z x!!}

Con una explicación:

{x y z:z y!z x!!}
{x y z:         }  three arguments
       z y!        apply `y` to `z` -- `y(z)`
           z x!    apply `x` to `z` -- `x(z)`
               !   apply `x(z)` to `y(z)` -- `x(z)(y(z))`

Y por lo tanto, este es el combinador S.