Discussion:Brainfuck

Une page de Wikipédia, l'encyclopédie libre.
Sauter à la navigation Sauter à la recherche
Autres discussions [liste]
  • Suppression
  • Neutralité
  • Droit d'auteur
  • Article de qualité
  • Bon article
  • Lumière sur
  • À faire
  • Archives

Spoon sans espace[modifier le code]

Je n'ai pas compris comment le spoon peut s'écrire sans espace, car il me semble que cela provoque des ambiguïtés à la lecture. Merci de compléter. domsau2 (d) 30 janvier 2011 à 18:24 (CET)

Aucune ambiguïté. Par exemple, si le premier bit est un 0 suivi d'un 1, il s'agit soit de < soit de >, donc exactement 3 bits, donc l'instruction suivante commance au 4ème bit.
Si on commence par un double 0 suivi d'un 1, le nombre de 0 qui suit est unique. On connait donc toujours la taille d'un instruction, donc où commence l'instruction suivante.
Je m'exprime peut-être mal, mais il suffit de tenter de décoder la suite illisible de 0 et de 1, on voit bien qu'il n'existe pas 36 000 possibilités, mais une seule.
Epok (d) 17 avril 2011 à 16:48 (CEST)
Les suites de bits n'ont pas été choisies au hasard :
Si on les classe dans l'ordre on obtient :
0000000
0010000
0010100
0010110
0011000
0100000
0110000
1000000
Soit un arbre permettant la lecture des bits de gauche à droite :
1er bit 2e bit 3e bit 4e bit 5e bit 6e bit 7e bit Instruction Valeur Hex
0 0 0 - 0x00
1 0 0 [ 0x04
1 0 . 0x14
1 0 , 0x34
1 0 ] 0x0C
1 0 > 0x02
1 0 < 0x06
1 0 + 0x01
Voir Codage entropique, Codage de Huffman et Codage de Shannon-Fano.
--DavidL (d) 12 octobre 2011 à 19:07 (CEST)

Turing-complet, récursivité et brainfuck[modifier le code]

Le postulat de Turing sur la complétude indique clairement que la Turing complétude d'un langage doit permettre de représenter toutes les fonctions calculables, y compris la récursion. https://en.wikipedia.org/wiki/Computable_function#Church%E2%80%93Turing_thesis

A mon sens, le Brainfuck ne permettant pas d'écrire de méthodes auto appelantes, le brainfuck n'est pas à proprement parler turring-complet malgré la soit distante preuve donnée car elle ne permet pas la récursion.

--Ppignol (discuter) 25 avril 2018 à 17:42 (CEST)

Toute fonction récursive peut être remplacée par une fonction non récursive, et faire exactement la même chose. Avec votre raisonnement, une machine de Turing n'est pas Turing complète, car elle ne permet pas (directement) la récursion ! Brainfuck ne permet pas (directement) la récursion, mais peut très bien implémenter toute fonction calculable récursive, par un algorithme itératif, comme toute machine de Turing. --Jean-Christophe BENOIST (discuter) 29 mai 2018 à 16:06 (CEST)