A palavra infinita de Fibonacci é uma sequência infinita específica de dígitos binários, calculada por concatenação repetida de palavras binárias finitas.

Vamos definir que uma sequência de palavras de Fibonacci-tipo (ou FTW sequência ) é qualquer sequência ⟨W _n ⟩ que é formado como se segue.

• Comece com duas matrizes arbitrárias de dígitos binários. Vamos chamar essas matrizes de W _-1 e W ₀ .

• Para cada n> 0 , deixar W _n ≔ W _n-1 ∥ W _N-2 , onde ∥ denota concatenação.

Uma conseqüência da definição recursiva é que W _n é sempre um prefixo de W _{n + 1} e, portanto, de todos os W _{k, de} modo que k> n . Num certo sentido, isso significa que a sequência ⟨W _n ⟩ converge para uma palavra infinito.

Formalmente, seja W _∞ ser a matriz só infinito de tal modo que W _n é um prefixo de W _∞ para todo n ≥ 0 .

Chamaremos qualquer palavra infinita formada pelo processo acima de FTW infinito .

Tarefa

Escreva um programa ou função que aceite duas palavras binárias W _-1 e W ₀ como entrada e imprima W _∞ , respeitando as seguintes regras adicionais:

• Você pode aceitar as palavras em qualquer ordem; como duas matrizes, uma matriz de matrizes, duas cadeias, uma matriz de cadeias ou uma única cadeia com um delimitador de sua escolha.

• Você pode imprimir os dígitos da palavra infinita sem um delimitador ou com um delimitador consistente entre cada par de dígitos adjacentes.

• Para todos os efeitos, suponha que seu código nunca fique sem memória e que seus tipos de dados não sejam excedidos.

  Em particular, isso significa que qualquer saída para STDOUT ou STDERR resultante de uma falha será ignorada.

• Se eu executar seu código na minha máquina (Intel i7-3770, 16 GiB RAM, Fedora 21) por um minuto e canalizar sua saída wc -c, ele deverá imprimir pelo menos um milhão de dígitos de W _∞ para (W _-1 , W ₀ ) = (1, 0) .

• Aplicam-se as regras de código-golfe padrão .

Exemplo

Seja W _-1 = 1 e W ₀ = 0 .

Então W ₁ = 01 , W ₂ = 010 , W ₃ = 01001 , W ₄ = 01001010 … e W _∞ = 010010100100101001001010… .

Esta é a palavra infinita de Fibonacci.

Casos de teste

Todos os casos de teste contêm os primeiros 1.000 dígitos do FTW infinito.

Input:  1 0
Output: 0100101001001010010100100101001001010010100100101001010010010100100101001010010010100100101001010010010100101001001010010010100101001001010010100100101001001010010100100101001001010010100100101001010010010100100101001010010010100100101001010010010100101001001010010010100101001001010010100100101001001010010100100101001001010010100100101001010010010100100101001010010010100101001001010010010100101001001010010010100101001001010010100100101001001010010100100101001001010010100100101001010010010100100101001010010010100101001001010010010100101001001010010010100101001001010010100100101001001010010100100101001001010010100100101001010010010100100101001010010010100101001001010010010100101001001010010010100101001001010010100100101001001010010100100101001010010010100100101001010010010100100101001010010010100101001001010010010100101001001010010010100101001001010010100100101001001010010100100101001010010010100100101001010010010100100101001010010010100101001001010010010100101001001010010100100101001001

Input:  0 01
Output: 0100101001001010010100100101001001010010100100101001010010010100100101001010010010100100101001010010010100101001001010010010100101001001010010100100101001001010010100100101001001010010100100101001010010010100100101001010010010100100101001010010010100101001001010010010100101001001010010100100101001001010010100100101001001010010100100101001010010010100100101001010010010100101001001010010010100101001001010010010100101001001010010100100101001001010010100100101001001010010100100101001010010010100100101001010010010100101001001010010010100101001001010010010100101001001010010100100101001001010010100100101001001010010100100101001010010010100100101001010010010100101001001010010010100101001001010010010100101001001010010100100101001001010010100100101001010010010100100101001010010010100100101001010010010100101001001010010010100101001001010010010100101001001010010100100101001001010010100100101001010010010100100101001010010010100100101001010010010100101001001010010010100101001001010010100100101001001

Input:  11 000
Output: 0001100000011000110000001100000011000110000001100011000000110000001100011000000110000001100011000000110001100000011000000110001100000011000110000001100000011000110000001100000011000110000001100011000000110000001100011000000110000001100011000000110001100000011000000110001100000011000110000001100000011000110000001100000011000110000001100011000000110000001100011000000110001100000011000000110001100000011000000110001100000011000110000001100000011000110000001100000011000110000001100011000000110000001100011000000110001100000011000000110001100000011000000110001100000011000110000001100000011000110000001100000011000110000001100011000000110000001100011000000110001100000011000000110001100000011000000110001100000011000110000001100000011000110000001100011000000110000001100011000000110000001100011000000110001100000011000000110001100000011000000110001100000011000110000001100000011000110000001100011000000110000001100011000000110000001100011000000110001100000011000000110001100000011000110000001100000011

Input:  10 010
Output: 0101001001010010100100101001001010010100100101001010010010100100101001010010010100100101001010010010100101001001010010010100101001001010010100100101001001010010100100101001001010010100100101001010010010100100101001010010010100100101001010010010100101001001010010010100101001001010010100100101001001010010100100101001001010010100100101001010010010100100101001010010010100101001001010010010100101001001010010010100101001001010010100100101001001010010100100101001001010010100100101001010010010100100101001010010010100101001001010010010100101001001010010010100101001001010010100100101001001010010100100101001001010010100100101001010010010100100101001010010010100101001001010010010100101001001010010010100101001001010010100100101001001010010100100101001010010010100100101001010010010100100101001010010010100101001001010010010100101001001010010010100101001001010010100100101001001010010100100101001010010010100100101001010010010100100101001010010010100101001001010010010100101001001010010100100101001001010

Input:  101 110
Output: 1101011101101011101011101101011101101011101011101101011101011101101011101101011101011101101011101101011101011101101011101011101101011101101011101011101101011101011101101011101101011101011101101011101101011101011101101011101011101101011101101011101011101101011101101011101011101101011101011101101011101101011101011101101011101011101101011101101011101011101101011101101011101011101101011101011101101011101101011101011101101011101011101101011101101011101011101101011101101011101011101101011101011101101011101101011101011101101011101101011101011101101011101011101101011101101011101011101101011101011101101011101101011101011101101011101101011101011101101011101011101101011101101011101011101101011101101011101011101101011101011101101011101101011101011101101011101011101101011101101011101011101101011101101011101011101101011101011101101011101101011101011101101011101011101101011101101011101011101101011101101011101011101101011101011101101011101101011101011101101011101101011101011101101011101011101101011101

Pitão, 8 bytes

u,peGsGQ

Entrada no formulário "W-1", "W0".

Prova de conclusão:

$ time pyth -cd 'u,peGsGQ' <<< '"1", "0"' 2>/dev/null | head -c1000000 > /dev/null

real    0m0.177s
user    0m0.140s
sys 0m0.038s

Prova de correção:

Aqui está a série gerada internamente. É impresso em concatenação pelo programa.

[0, 10, 010, 10010, 01010010, 1001001010010,...]

Compare com o seguinte, impresso em concatenação, que é simplesmente a sequência adicionada à sequência anterior em cada etapa:

[0, 1, 0, 01, 010, 01001, 01001010, 0100101001001, ...]

Queremos provar que são equivalentes.

Claramente, eles são os mesmos através dos primeiros passos. Vamos compará-los depois de um pouco:

010
  010

10010
  01001

01010010
  01001010

1001001010010
  0100101001001

Vemos que os pares de cordas são alternadamente das formas:

01a 10b
a10 b01

Onde aeb são seqüências arbitrárias em 0s e 1s. Vamos continuar a sequência um pouco, para provar que continua para sempre por indução:

01a   10b   10b01a   10b01a10b
  a10   b01   a10b01   b01a10b01

2 etapas depois, é da forma correta.

10b   01a   01a10b   01a10b01a
  b01   a10   b01a10   a10b01a10

2 etapas depois, é da forma correta.

Portanto, por indução, as cordas sempre correspondem uma vez concatenadas.

Haskell, 15 bytes

v%w=w++w%(v++w)

A função infix %produz uma sequência infinita, que Haskell imprime para sempre porque Haskell é legal assim.

>> "1"%"0"
"010010100100101001010010010100100101001010010010100101001001010010010100101001001010010010100101001001010010100100101001001010010100100101001010010010100100101001010010010100100101001010010010100101001001010010010100101001001010010010100101001001010010100100101001001010010100100101001010010010100100101001010010010100100101001010010010100101001001010010010100101001001010010100100101001001010010100100101001001010010100100101001010010010100100101001010010010100100101001010010010100101001001010010010100101001001010010100100101001001010010100100101001001010010100100101001010010010100100101001010010010100100101001010010010100101001001010010010100101001001010010100100101001001010010100100101001001010010100100101001010010010100100101001010010010100101001001010010010100101001001010010010100101001001010010100100101001001010010100100101001001010010100100101001010010010100100101001010010010100101001001010010010100101001001010010010100101001001010010100100101001001010010100100101001010010010100100101001010010010100100101

A ideia recursiva é semelhante à solução do Zgarb . Escrevendo fpara a função %e +para concatenação de cadeias, ele implementa:

f(v,w) = w + f(w,v+w)

A seqüência de saída infinita começa com w, e o restante é o resultado das seqüências de Fibonacci we v+w.

Isso não tem problema em gerar um milhão de caracteres em um minuto.

Haskell, 31 bytes

w#v=v++drop(length v)(v#(v++w))

Isso define uma função infix #que pega duas cadeias e retorna uma cadeia infinita. Uso:

> let w#v=v++drop(length v)(v#(v++w)) in "11"#"000"
"000110000001100011000000110000...

Se eu consultar o milionésimo elemento da sequência definida por "1" e "0", até o intérprete online imprimirá o resultado em menos de um segundo:

> let w#v=v++drop(length v)(v#(v++w)) in ("1"#"0") !! 1000000
'0'

Explicação

w#v=                             -- The result of w#v is
    v++                          -- v concatenated to
                      v#(v++w)   -- the infinite word v#(v++w),
       drop(length v)            -- with the first v characters dropped.

Basicamente, sabemos disso w#v == v#(v++w)e w#vcomeça com v, e usamos esses fatos para definir o resultado. Como Haskell é preguiçoso, isso "magicamente" simplesmente funciona.

Pip, 8 bytes

Ei, amarrado com Pyth!

(fOba.b)

Definição recursiva direta emprestada da resposta Haskell do xnor . Com espaços adicionados para maior clareza:

(f Ob a.b)

Cada programa em Pip é uma função implícita que leva os argumentos de linha de comando como seus argumentos (atribuídos às variáveis aatravés e) e imprime seu valor de retorno. Oé um operador que gera e retorna seu operando; portanto, a primeira coisa que acontece aqui é o segundo argumento (sem nova linha).

Agora, a sintaxe inspirada no Lisp (f x y)no Pip é uma chamada de função, equivalente a f(x,y)linguagens do tipo C. A fvariável refere-se à função atual - neste caso, o programa de nível superior. Assim, o programa se chama recursivamente com be a.bcomo novos argumentos.

Fiquei agradavelmente surpreso ao descobrir que essa abordagem é bastante rápida:

dlosc@dlosc:~$ time pip -e '(fOba.b)' 1 0 2>/dev/null | head -c1000000 > /dev/null

real    0m0.217s
user    0m0.189s
sys     0m0.028s

Leva cerca de 30 segundos na minha máquina Ubuntu para que o programa atinja a profundidade máxima de recursão, momento em que foi impresso em algum lugar com mais de um bilhão de dígitos.

Essa solução iterativa é um pouco mais rápida e consome menos memória, ao custo de um byte:

W1Sba.:Ob

CJam, 12 11 bytes

llL{@_o+_}h

Isso leva as duas palavras em linhas separadas, na ordem oposta, por exemplo

0
1

dá

0100101001001010010100100101001...

Explicação

A idéia é construir a palavra ingenuamente (lembrando a palavra atual e anexando a anterior) e enquanto fazemos isso, imprimimos o que acabamos de acrescentar (para não repetir o prefixo que já foi impresso) . Para evitar ter que lidar com o ponto de partida separadamente, partimos de uma palavra vazia, de modo que W ₀ seja a primeira coisa que anexamos (e imprimimos).

ll    e# Read the two lines separately.
L     e# Push an empty string.
{     e# Infinite loop...
  @   e#   Pull up the previous FTW.
  _o  e#   Print it.
  +_  e#   Append it to the current FTW and duplicate it.
}h

PowerShell, 97 76 bytes

param($a,$b)write-host -n $b;while(1){write-host -n $a;$e=$b+$a;$a=$b;$b=$e}

_{Editar - Umm, escrever $e.substring($b.length)depois de termos concatenado $ae $bjuntos é equivalente a escrever apenas $a... derp.}

Uau, detalhado. O PowerShell, por padrão, cuspirá uma nova linha toda vez que você produzir algo. Realmente a única maneira de contornar isso é com write-host -n(abreviação de -NoNewLine), e que absolutamente mata o comprimento aqui.

Essencialmente, este percorre a seqüência, construindo $ecomo o "atual" W _n à medida que avançamos. No entanto, como queremos construir a palavra infinita em vez da sequência, aproveitamos nossas variáveis ​​anteriores para imprimir o sufixo $apreenchido em nosso loop anterior. Em seguida, configuramos nossas variáveis ​​para a próxima rodada e repetimos o loop. Observe que isso espera que a entrada seja explicitamente delimitada como strings; caso contrário, o +operador será usado para aritmética em vez de concatenação.

Exemplo:

PS C:\Tools\Scripts\golfing> .\infinite-ftw.ps1 "111" "000"
0001110000001110001110000001110000001110001110000001110001110000001110000001110001110000001110000001110001110000001110001110000001110000001110001110000001110001110000001110000001110001110000001110000001110001110000001110001110000001110000001110001110000001110000 ...

APL, 24 18

{(,/⌽⍵),⊂⍞←↑⍵}⍣≡⍞⍞

O uso da formulação do xnor permitiu raspar poucos caracteres.

                 ⍞  ⍝ Read W₋₁ as a character string.
                ⍞   ⍝ Read W₀.
{            }⍣≡    ⍝ Apply the following function repeatedly until fixpoint:
                    ⍝ It takes a pair of strings (A B),
         ⍞←↑⍵       ⍝ prints A
 (,/⌽⍵),⊂  ↑⍵       ⍝ and returns (BA A).

Em uma máquina infinita em tempo infinito, na verdade, ele _imprimia W três vezes - primeiro incrementalmente ao executar o loop e, em seguida, duas vezes como resultado de toda a expressão quando o ⍣≡operador do ponto de fixação finalmente retorna.

Não é muito rápido, mas rápido o suficiente. No GNU APL:

$ printf '%s\n' '{(,/⌽⍵),⊂⍞←↑⍵}⍣≡⍞⍞' 1 0 | apl -s | head -c 100
0100101001001010010100100101001001010010100100101001010010010100100101001010010010100100101001010010$
$ time printf '%s\n' '{(,/⌽⍵),⊂⍞←↑⍵}⍣≡⍞⍞' 1 0 | apl -s | head -c 1000000 >/dev/null
    0m3.37s real     0m2.29s user     0m1.98s system

Pure bash, 58

a=$1
b=$2
printf $b
for((;;)){
printf $a
t=$b
b+=$a
a=$t
}

Fico sem memória antes de 1 minuto, mas já tenho muitos dígitos - depois de 10 segundos, tenho 100 milhões de dígitos:

$ ./ftw.sh 1 0 | head -c100
0100101001001010010100100101001001010010100100101001010010010100100101001010010010100100101001010010ubuntu@ubuntu:~$ 
$ { ./ftw.sh 1 0 & sleep 10 ; kill $! ; } | wc -c
102334155
$ 

Mathematica, 56 bytes

$IterationLimit=∞;#0[$Output~WriteString~#2;#2,#<>#2]&

C, 76 (gcc)

main(c,v)char**v;{int p(n){n>2?p(n-1),p(n-2):puts(v[n]);}for(p(4);;p(c++));}

Esta é uma impressora recursiva bastante simples, implementada como uma função aninhada (uma extensão GNU C não suportada pelo clang) para evitar ter que passar por vaí. p(n)imprime W _n-2 , onde W _-1 e W ₀ devem ser fornecidos emv[1]ev[2]. Isso inicialmente chamap(4)para imprimir W ₂ . Em seguida, faz um loop: chamap(3)para imprimir W ₁ , produzindo a saída completa W ₂ W ₁ , que é W ₃ . Em seguida, ele chamap(4)para imprimir W ₂ , produzindo a saída completa W₄ , etc. O desempenho é um pouco melhor do que minha resposta anterior: estou vendo 1875034112 valores em um minuto.

C, 81 (toque)

Essa é uma abordagem completamente diferente da acima, que eu acho que vale a pena acompanhar, mesmo que a pontuação seja pior.

s[],*p=s;main(c,v)char**v;{for(++v;;)for(puts(v[*++p=*++p!=1]);*p+1==*--p;++*p);}

Isso tem todos os tipos de comportamento indefinido, principalmente por diversão. Ele funciona com o clang 3.6.2 no Linux e com o clang 3.5.2 no Cygwin para os casos de teste da pergunta, com ou sem opções especiais de linha de comando. Não quebra quando as otimizações estão ativadas.

Não funciona com outros compiladores.

Você pode aceitar as palavras em qualquer ordem; como duas matrizes, uma matriz de matrizes, duas cadeias, uma matriz de cadeias ou uma única cadeia com um delimitador de sua escolha.

Eu aceito as palavras como argumentos de linha de comando no formato de string.

Você pode imprimir os dígitos da palavra infinita sem um delimitador ou com um delimitador consistente entre cada par de dígitos adjacentes.

Eu uso nova linha como delimitador consistente.

Para todos os efeitos, suponha que seu código nunca fique sem memória e que seus tipos de dados não sejam excedidos.

Em particular, isso significa que qualquer saída para STDOUT ou STDERR resultante de uma falha será ignorada.

Eu acesso sfora dos limites. Isso certamente deve terminar com um segfault ou uma violação de acesso em algum momento. spassa a ser colocado no final do segmento de dados, portanto, não deve prejudicar outras variáveis ​​e fornecer saída incorreta antes desse segfault. Esperançosamente.

Se eu executar o seu código na minha máquina (Intel i7-3770, 16 GiB RAM, Fedora 21) por um minuto e canalizar sua saída para wc -c, ele deverá imprimir pelo menos um milhão de dígitos de W _∞ para (W _-1 , W ₀ ) = (1, 0) .

Testando usando { ./program 1 0 | tr -d '\n' & sleep 60; kill $!; } | wc -c, recebo 1816784896 dígitos em um minuto na minha máquina quando o programa foi compilado -O3e 1596678144 quando foi compilado com otimizações em diamantes.

Ungolfed, no UB, com explicação:

#include <stdio.h>

// Instead of starting with -1 and 0, start with 0 and 1. I will use lowercase w for that,
// so that wx = W(x-1).

// Declare a variable length array of numbers indicating what has been printed.
// The length is indicated through a pointer just past the end of the values.
// The first element of the array is a special marker.
// [0 3 1] means that w3 w1 has been printed.
// The array is initialised to [0] meaning nothing has been printed yet.
int stack[99999];
int *ptr = stack + 1;

int main(int argc, char *argv[]) {
  ++argv; // Let argv[0] and argv[1] refer to w0 and w1.
  for(;;) {
    // Determine the word to print next, either 0 or 1.
    // If we just printed 1 that wasn't the end of a different word, we need to print 0 now.
    // Otherwise, we need to print 1.
    int word = ptr[-1] != 1;

    // Print the word, and mark the word as printed.
    puts(argv[word]);
    *ptr++ = word;

    // If we just printed w(x) w(x-1) for any x, we've printed w(x+1).
    while (ptr[-1] + 1 == ptr[-2]) {
      --ptr;
      ++ptr[-1];
    }
  }
}

Javascript (53 bytes)

(a,c)=>{for(;;process.stdout.write(a))b=a,a=c,c=b+a;}

A entrada deve ser string e não número ( '0'e não apenas 0).

Perl 5, 45 55 49 bytes

44 bytes, mais 1 para em -Evez de-e

sub{$i=1;{say$_[++$i]=$_[$i].$_[$i-1];redo}}

Use como por exemplo

perl -E'sub{$i=1;{say$_[++$i]=$_[$i].$_[$i-1];redo}}->(1,0)'

Isso imprime aproximações sucessivas de W _∞ e, portanto, se você esperar o suficiente, imprime, em sua última linha de saída, W _∞ no comprimento desejado, conforme necessário. Os dígitos da palavra são concatenados sem um delimitador.

Como estou no Windows, testei o requisito "pelo menos um milhão de dígitos de W _∞ ", executando-o com saída redirecionada para um arquivo e matando-o após cerca de 59 segundos, depois executando o GnuWin32 wc -L, que imprimiu 701408733.

Atualizar:

O OP esclareceu em um comentário sobre esta resposta (e provavelmente eu deveria ter percebido qualquer maneira) que a saída adicional anterior W _∞ desqualifica o acima. Então, aqui está uma solução de 55 bytes que imprime apenas W _∞ :

sub{print$_[0];{print$_[1];unshift@_,$_[0].$_[1];redo}}

Usado da mesma maneira, mas com os argumentos na ordem inversa e não requer -E:

perl -e'sub{print$_[0];{print$_[1];unshift@_,$_[0].$_[1];redo}}->(0,1)'

Sem dúvida, ele pode ser jogado ainda mais, mas não vejo como fazê-lo agora.

Atualização adicional:

Dennis raspou cinco bytes usando -a(lendo <>para remover sub) e reatribuindo o parâmetro passado printno final do redobloco:

Com -anee lendo de <>(ambas as entradas em uma linha, separadas por espaço, na ordem inversa); 48 + 2 bytes:

$_=$F[0];{print;unshift@F,$F[0].($_=$F[1]);redo}

E, com base nisso, raspei mais um byte (o mesmo que acima, mas agora as entradas estão na ordem correta); 47 + 2 bytes:

$_=$F[1];{print;push@F,$F[-1].($_=$F[-2]);redo}

REXX , 48

arg a b
do forever
b=a||b
say b
a=b||a
say a
end

ftw.rex
exec ftw.rex 0 1

Atualmente não posso testar o desempenho porque usei um compilador online para escrevê-lo. O "para sempre" pode ser substituído por qualquer número onde estão os números de ftw impressos (número + 2).

Também escrevi uma solução pequena (bagunçada) no Prolog. Não imaginou como testar o desempenho com este, mas provavelmente é atroz de qualquer maneira.

f(A,B,C):-atom_concat(B,A,D),(C=D;f(B,D,C)).

:- C='0';C='1';(f(1,0,C)).

Python 2, 67 bytes

a,b=input()
print'\n'.join(b+a)
while 1:a,b=b,b+a;print'\n'.join(a)

Aceita entrada como um par de seqüências de caracteres separadas por vírgula: "1","0" por exemplo, na pergunta.

Não há intérprete on-line porque loops infinitos são ruins. A saída em buffer me fez ganhar muitos bytes. :( Obrigado Dennis por apontar que 1 dígito por linha é válido.

Tempo na minha máquina (significativamente mais fraca):

$ time python golf.py <<< '"1","0"' 2>/dev/null | head -c2000000 > /dev/null

real    0m1.348s
user    0m0.031s
sys     0m0.108s

Dyalog APL, 9

{⍵∇⍺,⍞←⍵}

Este usa ∇para definir uma função recursiva. É uma tradução direta da resposta Python 3 deste xnor . Leva W ₀ à direita e W _-1 como argumento à esquerda, ambos devem ser vetores de caracteres.

Minkolang 0.11 , 62 bytes

(od" "=,6&xI0G2@dO$I)I1-0G($d2[I2:g]Xx0c2*1c-0g0g-d[icO]0G0G1)

Experimente aqui. Espera entrada na ordem W ₀ , W _-1 com um espaço no meio.

Explicação

(                             Open while loop (for input-reading)
 od                           Read in character from input and duplicate
   " "=,                      0 if equal to " ", 1 otherwise
        6&                    Jump 6 characters if this is non-zero
          xI0G2@              Dump, push length of stack, move to front, and jump next two
                dO            Duplicate and output as character if 1
                  $I)         Close while loop when input is empty
                     I1-0G    Push length of stack - 1 and move it to the front

A meta-explicação para o seguinte é que, neste momento, temos dois números seguidos por uma sequência de "0" se "1" s sem separação. Se os comprimentos de W ₀ e W _-1 forem ae b, respectivamente, os dois números na frente da pilha são <a+b>e <a>, nessa ordem. A palavra formada concatenando W _{i + 1} e W _i , ou seja, W _{i + 1} + W _i , é igual a 2 * W _{i + 1} - W _i . Portanto, o código a seguir duplica a pilha (2 * W _{i + 1} ), aparece em cima<a> elementos (- W_i) e, em seguida, substitui <a+b>e<a>com seus sucessores <a+2b>e <b>.

(                                       Open while loop (for calculation and output)
 $d                                     Duplicate the whole stack
   2[I2:g]                              Pull <a+b> and <a> from the middle of the stack
          Xx                            Dump the top <a> elements (and <a+b>)
            0c2*1c-                     Get <a+b> and <a>, then calculate
                                        2*<a+b> - <a> = <a+2b> = <a+b> + <b>
                   0g0g-                Get <a+b> and <a>, then subtract
                        d[icO]          Output as character the first <b> elements
                              0G0G      Move both to front
                                  1)    Infinite loop (basically, "while 1:")

Python 3, 32

def f(a,b):print(end=b);f(b,a+b)

A mesma ideia recursiva da minha resposta Haskell , exceto o prefixo, é impressa porque o Python não pode lidar com seqüências infinitas.

Utilizou um truque do Sp3000 para imprimir sem espaços, colocando a string como endargumento em Python 3

Perl, 32 bytes

#!perl -pa
$#F=3}for(@F){push@F,$F[-1].$_

Contando o shebang como dois, a entrada é obtida de stdin, o espaço é separado como W ₀ , W _-1 . Saída por 1 MB de tempo a ~ 15 ms, a maioria dos quais pode ser atribuída ao lançamento do intérprete.

Uso da amostra

$ echo 0 1 | perl inf-ftw.pl
0100101001001010010100100101001001010010100100101001010010010100100101001010010010100100101001010010010100101001001010010010100101001001010010100100101001001010010100100101001001010010100100101001010010010100100101001010010010100100101001010010010100101001001010010010100101001001010010100100101001001010010100100101001001010010100100101001010010010100100101001010010010100101001001010010010100101001001010010010100101001001010010100100101001001010010100100101001001010010100100101001010010010100100101001010010010100101001001010010010100101001001010010010100101001001010010100100101001001010010100100101001001010010100100101001010010010100100101001010010010100101001001010010010100101001001010010010100101001001010010100100101001001010010100100101001010010010100100101001010010010100100101001010010010100101001001010010010100101001001010010010100101001001010010100100101001001010010100100101001010010010100100101001010010010100100101001010010010100101001001010010010100101001001010010100100101001001...

$ echo 110 101 | perl inf-ftw.pl
1101011101101011101011101101011101101011101011101101011101011101101011101101011101011101101011101101011101011101101011101011101101011101101011101011101101011101011101101011101101011101011101101011101101011101011101101011101011101101011101101011101011101101011101101011101011101101011101011101101011101101011101011101101011101011101101011101101011101011101101011101101011101011101101011101011101101011101101011101011101101011101011101101011101101011101011101101011101101011101011101101011101011101101011101101011101011101101011101101011101011101101011101011101101011101101011101011101101011101011101101011101101011101011101101011101101011101011101101011101011101101011101101011101011101101011101101011101011101101011101011101101011101101011101011101101011101011101101011101101011101011101101011101101011101011101101011101011101101011101101011101011101101011101011101101011101101011101011101101011101101011101011101101011101011101101011101101011101011101101011101101011101011101101011101011101101011101...

Prolog, 69 bytes

q(A,B):-atom_concat(B,A,S),write(A),q(B,S).
p(A,B):-write(B),q(A,B).

Exemplo de entrada: p ('1', '0')

Não foi possível remover a gravação extra.
Deveria ser capaz de melhorar isso, se eu descobrir como fazer isso.