Le «degré de difficulté de Rabin à calculer une fonction et un ordre partiel des ensembles récursifs»

13

Je cherche:

  • Michael O. Rabin, "Degré de difficulté de calcul d'une fonction et ordre partiel d'ensembles récursifs", Université hébraïque, Jérusalem, 1960

Sommaire:

«Nous essayons de mesurer la quantité de travail inhérente à la tâche de calculer une fonction calculable (récursive) donnée. Une notion de degré de difficulté de calcul est introduite et étudiée. La notion est invariante dans le sens où elle est indépendante des calculateurs idéalisés (Turing Machines) utilisés pour calculer les fonctions en question. Des applications sont faites à la classification des problèmes de décision résolubles (ensembles récursifs) en fonction de la difficulté relative. »

Je n'ai pas trouvé de copie en ligne ou à notre bibliothèque.

cc.complexity-theory reference-request ho.history-overview Kaveh
la source
1
Le titre est intéressant et la thèse devrait donner un aperçu du développement précoce des notions qui capturent la dureté des fonctions informatiques.
Mohammad Al-Turkistany
2
J'espère qu'ils gardent une copie physique à l'Université hébraïque ...
Yuval Filmus
Un commentaire qui ne concerne pas (directement) le PO: est-il légal de collecter un référentiel en ligne d'anciennes thèses / dissertations (je ne sais pas combien de temps est qualifié d'ancien) et de permettre un accès gratuit? Pour de nombreuses raisons, les plus récentes sont généralement faciles à obtenir.
Yixin Cao du
Les commentaires @YixinCao ne conviennent pas pour poser de nouvelles questions tangentielles. Vous pouvez poser une question sur Academia .
Kaveh
ps: il s'avère que ce n'est pas la thèse de Rabin. Sa thèse selon Wikipedia est "Insolvabilité récursive des problèmes théoriques de groupe", 1957.
Kaveh

Réponses:

14

Il existe deux exemplaires prêtables à la Bibliothèque nationale d'Israël.

Voici une copie numérisée .

Yuval Filmus
la source
1
Agréable. S'agit-il de copies papier? Offrent-ils une version PDF?
Mohammad Al-Turkistany
2
Des copies papier. Mais peut-être les scanneront-ils à la demande. Je peux probablement me procurer une copie physique moi-même, bien que je ne vais pas tout numériser par moi-même ...
Yuval Filmus
3
Merci Yuval. J'espère que quelqu'un a une copie scannée (considérant que c'est une des références fondatrices de la théorie de la complexité).
Kaveh
@Kaveh: Est-ce l'une des références fondatrices? Je ne l' ai jamais vu cité ... J'ai une analyse de « mathématique théorie des automates, » de Rabin qui est l' un des trois documents souvent cités pour avoir introduit la notion de P (et que je donc faire considère fondamental). Faites-moi savoir si vous le souhaitez.
Joshua Grochow
@Josh, je l'ai vu cité avec Cobham et Edmonds et Hartmanis et Stearns comme premiers articles parlant de ce qu'on appelle maintenant la théorie de la complexité computationnelle. Heureusement, Steve a une copie de la thèse de Rabin, il a dit qu'il la numériserait et la publierait en ligne.
Kaveh