Turing-completezza di una versione modificata di Brainfuck

Question

Is Brainfuck Turing-complete se le celle sono bit e le operazioni + e - semplicemente capovolgono un po '? C'è una semplice dimostrazione che le lingue simili a Brainfuck sono complete di Turing indipendentemente dalle dimensioni della cella o devo pensare a un programma che simula una macchina di Turing? Come potrei sapere se non ce n'è uno?

MODIFICA: Ho trovato una risposta alla mia domanda: Brainfuck con celle a bit è chiamato Boolfuck. Ordinary Brainfuck può essere ridotto ad esso, quindi Boolfuck è completo di Turing.

Answer 1

Una lingua completa di Turing può "simulare qualsiasi macchina di Turing a nastro singolo". Brainfuck e Boolfuck sono entrambi completi di Turing, perché seguono le specifiche.

Si noti inoltre che se uno è completo di Turing, l'altro deve essere perché sono quasi la stessa. Con brainfuck, stai spostando in byte, ma in boolfuck, stai usando bit, che costituiscono byte.

Answer 2

This answer dovrebbe andare bene; ha una definizione molto specifica di quali caratteristiche rendono completo il linguaggio.

Ecco l'essenza di esso:

In generale, per un linguaggio imperativo di essere Turing-complete, di cui ha bisogno:

1. Una forma di ripetizione condizionale o di salto condizionato (ad esempio, while, if + goto)

2. Un modo per leggere e scrivere qualche forma di stoccaggio (ad esempio, variabili, nastro)