Turing Complete: Salvando graciosamente com guia de circuitos de atraso

Um passo a passo de um dos níveis mais difíceis de Turing Complete para grep.

 

Passo 1: O que temos que fazer?

De acordo com nosso amigo alienígena de nariz comprido, estamos construindo um circuito que pode salvar um valor e produzir qualquer valor atualmente salvo.

Resumindo um pouco mais, há algumas tarefas diferentes que realmente precisamos fazer aqui. Primeiro, precisamos de alguma forma salvar um valor para sempre. Em segundo lugar, se o bit “save” (a entrada superior) estiver ativado, precisamos substituir o que estiver “salvo” pelo valor no bit inferior.

Essa segunda parte parece complicada, mas vamos começar com a primeira e ver como podemos construir isso.

Etapa 2: vamos supor que salvar está desativado (e resolver um problema que já resolvemos antes)

Lembre-se de Odd Ticks? Nesse problema estávamos produzindo um WOW! e depois usando um NÃO para “salvar” um on, e então no próximo tick fazendo a mesma coisa mas com valores opostos. Isso parece complicado, então vamos usar uma imagem.


Neste caso, estávamos essencialmente salvando o resultado da NÃO do valor do último tick. Uma maneira de pensar sobre isso é que estamos produzindo o que quer que esteja no circuito de atraso, e colocando a saída que queremos para o próximo tick no circuito de atraso. Portanto, a maneira óbvia de salvar um valor aqui seria apenas fazer um loop de volta em si mesmo. Vamos tentar isso.


Ótimo, agora temos um loop de salvamento. Qualquer que seja a saída do circuito de atraso será alimentado de volta para ele, e seremos de ouro. Para simplificar, vou me referir a qualquer entrada que estamos enviando para o circuito de atraso como “salvando” a entrada.

Podemos testar isso? Com certeza, é uma boa ideia. Executando para WOW! funciona (até que os testes abaixo falhem, mas podemos ver que não há razão para ele virar de repente on e emitir um on sinal). Vamos lançar um on gerador e certifique-se de que ele salva um on.


Claro que não seria tão fácil :/ Nada amigável OR não pode consertar.


Isso é melhor! eu conheço o On faria isso on independentemente, mas espero que você possa ver, mesmo que pudéssemos levar isso on afastado, a entrada inferior para o OR manteria para sempre.

De fato, nos casos em que o salvar entrada is WOW!, este é exatamente o comportamento que queremos! Ou de outra forma, se o Salvar entrada is WOW! o valor salvo é on, em seguida, envie um on ao circuito de atraso, ou se o Salvar entrada is WOW! o valor salvo é WOW!, saída um WOW!. Podemos simplificar um pouco; se o Salvar entrada is WOW!, em seguida, envie o que estiver no circuito de atraso de volta para si mesmo, para que possamos produzi-lo no próximo tick.

Vamos fazer uma Tabela Verdade (aquelas coisas nos níveis anteriores que mostram qual deve ser a saída para determinadas entradas).

Salvar entrada
Entrada de loop salva
saída

Eu encorajo você a tentar construir isso sozinho, mas veja como isso pode parecer:


Aqui estou usando laranja para significar nosso loop de salvamento e azul claro para mostrar nosso salvar entrada. Eu recomendo adquirir o hábito de colorir os fios em grupos lógicos como este, você ficará feliz por ter feito nos níveis posteriores 🙂

Etapa 3: Ok, vamos adicionar a capacidade de alterar o que salvamos

Querido, temos metade do problema resolvido. Agora só precisamos descobrir como ignorar o que salvamos quando o salvar entrada is on, e em vez disso, salve o que estiver no entrada de valor. Isso parece difícil, mas vamos começar a brincar.


Bem, na verdade, olhando para o nosso circuito novamente, temos mais da metade do problema resolvido! Se o salvar entrada is on, Em seguida, o E garantirá que tudo o que salvamos esteja definido como WOW!. Neste caso, tudo o que precisamos fazer é pegar o valor do entrada de valor e escrevê-lo para o circuito de atraso.


Ahh, estamos tão perto, mas há um erro aqui. Estamos economizando o valor do entrada de valor, mesmo quando o salvar entrada não está definido. Nós só queremos salvar esse valor se o salvar entrada está ativado, então vamos usar alguma lógica novamente para descobrir como.

Salvar entrada
Entrada de valor
saída

Olhando para trás em nossa lógica de salvamento, queríamos o valor salvo se o salvar entrada foi WOW!. Aqui queremos o entrada de valor, se o salvar entrada is on. Isso soa notavelmente semelhante, então vamos tentar um portão novamente.


Aperte o play e… terminamos!

Outro

Esta não é a maneira mais eficiente de resolver o nível, mas esse não é o ponto. Eu queria mostrar os passos que você pode seguir para resolvê-lo sozinho, para que você possa entender o nível e não apenas obter um botão “pular”. No entanto, explicar as coisas não é minha habilidade mais forte, portanto, se houver algo que ainda não esteja claro, ou uma maneira diferente de pensar que o fez clicar para você, compartilhe nos comentários abaixo!

Este nível é difícil porque é um dos primeiros que exige que você divida o problema em subproblemas sem tornar óbvio que você deveria. Ser capaz de olhar para um problema e simplificá-lo até os subproblemas menores e mais fáceis o levará mais longe neste jogo do que qualquer grau de CS ou conhecimento de computação, então eu recomendo manter isso em mente em níveis futuros, onde os problemas aumentam e maior.

By Renwallz

1 pensou em “Turing completo: economizando graciosamente com guia de circuitos de atraso”

  1. OH MEU DEUS! Esta solução é tão sofisticada e satisfatória. Muito obrigado. Me ajudou muito a passar desse nível. Afirmativo!

    Resposta

Deixe um comentário

ArabicEnglishFrenchGermanItalianJapaneseKoreanPortugueseSpanish