Complétude de Turing de Catnip

Définition

Un langage de programmation est Turing-complet s'il peut simuler une machine de Turing universelle, c'est-à-dire s'il peut calculer toute fonction calculable.

Pour être Turing-complet, un langage doit posséder :

1. Stockage arbitraire de données - Mémoire illimitée (théoriquement)
2. Structures conditionnelles - Branchement basé sur des conditions
3. Boucles arbitraires - Itération sans limite connue à l'avance
4. Opérations arithmétiques et logiques - Manipulation de données
5. Optionnel mais utile : Récursion ou fonctions de première classe

Catnip satisfait tous les critères

1. Stockage arbitraire

Catnip permet de stocker des données de manière illimitée via :

• Variables dynamiques : x = 10, a = b = c = 42
• Collections Python : accès à list(), dict(), tuple(), set()
• Mémoire théoriquement illimitée (limitée uniquement par le système)

# Variables
compteur = 0
nom = "Alice"
valeurs = list(range(1000))

# Assignation en chaîne
a = b = c = 42

2. Structures conditionnelles

Catnip offre plusieurs mécanismes de branchement :

If/elif/else

if x > 0 {
    print("positif")
} elif x < 0 {
    print("négatif")
} else {
    print("zéro")
}

Pattern matching avec guards

match age {
    n if n < 18 => { print("Mineur") }
    n if n < 65 => { print("Adulte") }
    n => { print("Senior") }
}

3. Boucles arbitraires

Catnip supporte deux types de boucles :

While - Itération conditionnelle

# Boucle potentiellement infinie
i = 0
while i < 100 {
    i = i + 1
}

# Conjecture de Collatz (nombre d'itérations inconnu)
n = 27
while n != 1 {
    if n % 2 == 0 {
        n = n / 2
    } else {
        n = 3 * n + 1
    }
}

For - Itération sur séquences

for i in range(100) {
    print(i)
}

for element in collection {
    print(element)
}

4. Opérations arithmétiques et logiques

Catnip possède un ensemble complet d'opérateurs :

Arithmétiques

addition = a + b
soustraction = a - b
multiplication = a * b
division = a / b
division_entiere = a // b
modulo = a % b
puissance = a ** b

Comparaisons

egal = a == b
different = a != b
inferieur = a < b
superieur = a > b
inf_egal = a <= b
sup_egal = a >= b

Logiques

et = a and b
ou = a or b
non = not a

Binaires

et_binaire = a & b
ou_binaire = a | b
xor_binaire = a ^ b
inversion = ~a
decalage_gauche = a << n
decalage_droite = a >> n

5. Récursion et fonctions de première classe

Catnip supporte les lambdas récursives et les fonctions de première classe :

# Lambda récursive - Factorielle
factorielle = (n) => {
    match n {
        0 | 1 => { 1 }
        n => { n * factorielle(n - 1) }
    }
}

print(factorielle(10))  # 3628800

# Fonction d'Ackermann (récursion complexe non primitive)
ackermann = (m, n) => {
    match m {
        0 => { n + 1 }
        m => {
            match n {
                0 => { ackermann(m - 1, 1) }
                n => { ackermann(m - 1, ackermann(m, n - 1)) }
            }
        }
    }
}

print(ackermann(3, 2))  # 29

Exemples de preuves

Exemple 1 : Conjecture de Collatz

La conjecture de Collatz démontre les boucles arbitraires (nombre d'itérations inconnu à l'avance).

collatz = (n) => {
    steps = 0
    valeur = n
    while valeur != 1 {
        if valeur % 2 == 0 {
            valeur = valeur / 2
        } else {
            valeur = 3 * valeur + 1
        }
        steps = steps + 1
    }
    steps
}

print("collatz(27) =", collatz(27))  # 111 étapes

Exemple 2 : Suite de Fibonacci

Fibonacci démontre la manipulation d'état multiple et les boucles conditionnelles.

fibonacci = (n) => {
    match n {
        0 => { 0 }
        1 => { 1 }
        n => {
            a = 0
            b = 1
            i = 2
            while i <= n {
                temp = a + b
                a = b
                b = temp
                i = i + 1
            }
            b
        }
    }
}

print("fibonacci(20) =", fibonacci(20))  # 6765

Exemple 3 : PGCD d'Euclide

L'algorithme d'Euclide démontre la récursion et les opérations arithmétiques.

pgcd = (a, b) => {
    match b {
        0 => { a }
        b => { pgcd(b, a % b) }
    }
}

print("pgcd(48, 18) =", pgcd(48, 18))  # 6

Exemple 4 : Test de primalité

Combine boucles, conditions, arithmétique et pattern matching.

est_premier = (n) => {
    match n {
        n if n < 2 => { False }
        2 => { True }
        n if n % 2 == 0 => { False }
        n => {
            diviseur = 3
            est_premier_local = True
            while diviseur * diviseur <= n {
                if n % diviseur == 0 {
                    est_premier_local = False
                }
                diviseur = diviseur + 2
            }
            est_premier_local
        }
    }
}

print("97 est premier ?", est_premier(97))  # True

Capacités théoriques

Étant Turing-complet, Catnip peut :

Calculer toute fonction calculable

• Algorithmes de tri, recherche, optimisation
• Calculs mathématiques arbitraires
• Simulations, automates cellulaires
• Interprètes et compilateurs pour d'autres langages

Simuler n'importe quelle machine de Turing

• Peut implémenter des automates à états finis
• Peut simuler des machines de Turing universelles
• Peut émuler d'autres langages Turing-complets

Résoudre tout problème décidable

• Si un problème est algorithmiquement résolvable, Catnip peut le résoudre
• Limité uniquement par les ressources (temps, mémoire) du système

Limites pratiques

Bien que Turing-complet théoriquement, Catnip a des limites pratiques :

Limites de performance

• Pas d'optimisation de tail-call : La récursion profonde peut causer un stack overflow
• Interprété : Plus lent que les langages compilés
• Pas de JIT : Pas d'optimisation à l'exécution

Limites de mémoire

• Limité par la mémoire RAM du système
• Pas de mémoire virtuelle infinie

Recommandations

Pour des algorithmes récursifs profonds, préférer les boucles itératives :

# Récursif (risque de stack overflow pour n grand)
factorielle_rec = (n) => {
    match n {
        0 | 1 => { 1 }
        n => { n * factorielle_rec(n - 1) }
    }
}

# Itératif (meilleure performance)
factorielle_iter = (n) => {
    resultat = 1
    i = 2
    while i <= n {
        resultat = resultat * i
        i = i + 1
    }
    resultat
}

Comparaison avec d'autres langages

* CSS3 + HTML est accidentellement Turing-complet via des règles complexes.

Concepts théoriques

• Machine de Turing (Wikipedia)
• Complétude de Turing (Wikipedia)
• Thèse de Church-Turing

Démonstration complète

Pour exécuter la démonstration complète de complétude de Turing :

# Télécharger et exécuter la démo
catnip docs/examples/turing_completeness.cat

La démonstration inclut :

1. Récursion (factorielle)
2. Boucles arbitraires (Collatz)
3. Récursion complexe (Ackermann)
4. État multiple (Fibonacci)
5. Pattern matching (calculatrice)
6. Algorithmes récursifs (PGCD)
7. Algorithmes complets (primalité)

Conclusion : Catnip est un langage de programmation Turing-complet, capable de calculer toute fonction calculable. Il possède tous les éléments requis par la définition théorique, ainsi que des fonctionnalités modernes (pattern matching, lambdas, fonctions de première classe) qui facilitent l'écriture d'algorithmes complexes.