Recherche sur le calcul Lambda

continue des exercices dans le livre Lambda Calculus, la question est la suivante:Recherche sur le calcul Lambda

Supposons un symbole de l'alphabet λ-calcul est toujours 0.5cm de large. Ecrire vers le bas un λ-terme avec une longueur inférieure à 20 cm ayant une forme normale avec une longueur à moins (10^10)^10 lightyear. La vitesse de la lumière est c = 3 * (10^10) cm/sec.

Je n'ai absolument aucune idée de ce qui doit être fait dans cette question. Quelqu'un peut-il s'il vous plaît me donner quelques pointeurs pour aider à comprendre la question et ce qui doit être fait ici? Veuillez ne pas résoudre ou mentionner la réponse finale.

En espérant une réponse.

Cordialement, Darkie

Source

2010-06-21 name_masked

Je pense que c'est une question valide car le lambda-calcul devient plus important pour la programmation, maintenant. –

Ne sachant pas quoi que ce soit au sujet du calcul lambda, je comprends la question suivante:

Vous devez écrire un λ-terme en moins de 20 cm, où un symbole est 0.5cm , ce qui signifie que vous avez droit à moins de 40 symboles. Ce λ-terme devrait s'étendre à une forme normale avec une longueur d'au moins (10^10)^10 = 10^100 années-lumière, ce qui donne (10^100) * 2 * 3 * (10^10) * 24 * 60 * 60 symboles. Fondamentalement, une fonction récursive très longue.

Source

2010-06-21 00:23:44 Femaref

Je pense que votre analyse est bien faite, et vous montrez suffisamment pour faciliter l'écriture de la solution. –

J'ai une question, comment puis-je être sûr que ma fonction récursive λ dépasserait ce nombre de symboles? Je veux dire, c'est trop de symboles pour assurer, n'est-ce pas? –

Oui, c'est trop difficile à tester - c'est exactement le but de la tâche. Vous devez définir une fonction qui se développe extrêmement rapidement. Un exemple pour une telle fonction serait la [fonction Ackermann] (http://en.wikipedia.org/wiki/Ackermann_function). Je ne sais pas jusqu'où cela s'applique en λ-Calcul. Occupé Beaver serait également une telle fonction, en croissance extrêmement rapide sur toutes les limites. – Femaref

Voici un autre indice: dans le lambda-calcul, la façon habituelle de représenter un entier est par son codage d'église, qui est une représentation unaire. Donc, si vous convertissez les distances en nombres, une chose qui ferait l'affaire serait une petite fonction qui, lorsqu'elle est appliquée à un petit nombre, se termine et produit un très grand nombre.

Source

2010-06-21 16:46:06

Répondre

Questions connexes