Supponendo che le "celle di memoria" di Brainfuck abbiano valori minimi e massimi *, basta mettere il numero in due celle, quindi continuare a incrementarne uno e continuare a decrementare l'altro finché uno di questi non raggiunge lo zero. C'è l'algoritmo del tuo segno.
Ora per la domanda generale. "Una macchina completa di Turing può calcolare tutte le funzioni" non è una grande definizione per iniziare perché la "funzione" è troppo vaga. Ciò ti permetterebbe di sostenere che Brainfuck non è completo di Turing perché è impossibile scrivere web server e browser web in esso, o che C ++ 03 non è completo di Turing perché è impossibile scrivere programmi multi-thread in esso (senza estensioni standard).
Imparare a dimostrare formalmente la completezza di Turing è qualcosa che si apprende meglio da un libro di testo sulla teoria del calcolo. Ma ci sono molte euristiche utili che puoi usare nella pratica, come ad esempio:
- La ramificazione condizionale è possibile in qualsiasi lingua completa di Turing.
- I loop che si eseguono per infinite iterazioni o arbitrariamente molte iterazioni finite sono possibili in qualsiasi lingua completa di Turing.
- Qualsiasi linguaggio completo di Turing può essere utilizzato per scrivere un programma che richiede una memoria infinita o una quantità arbitrariamente grande di memoria.
- Tutte le lingue complete di Turing supportano almeno un qualche tipo di input e output per i loro programmi.
- Il problema dell'arresto è irrisolvibile per qualsiasi lingua completa di Turing. In altre parole, è impossibile scrivere un programma che possa guardare ad altri programmi e dire con certezza se sono in grado o meno di entrare in un ciclo infinito.
Brainfuck soddisfa tutti questi criteri. La maggior parte delle implementazioni di Brainfuck falliscono probabilmente i criteri di memoria, ma tale argomento si applica a tutti i linguaggi di programmazione poiché nel mondo reale i computer hanno sempre una memoria finita.
* Tecnicamente, lo standard non ufficiale di Brainfuck consente un'implementazione "bignum", e io sto anche ignorando la possibilità di inserire un numero che non rientra in una cella di memoria per un'implementazione non bignum. Ma ho deciso di non farmi nerd-snipe con quei problemi per ora; Sono abbastanza sicuro che possano essere risolti se lo volessimo davvero.