„Stopień trudności Rabina w obliczeniu funkcji i częściowe uporządkowanie zbiorów rekurencyjnych”

13

Szukam:

  • Michael O. Rabin, „Stopień trudności obliczenia funkcji i częściowe uporządkowanie zbiorów rekurencyjnych”, Uniwersytet Hebrajski, Jerozolima, 1960

Streszczenie:

„Próbujemy zmierzyć ilość pracy związanej z obliczeniem danej funkcji obliczeniowej (rekurencyjnej). Wprowadzono i zbadano pojęcie stopnia trudności obliczeń. Pojęcie to jest niezmienne w tym sensie, że jest niezależne od wyidealizowanych komputerów (maszyn Turinga) używanych do obliczania danych funkcji. Stosuje się wnioski dotyczące klasyfikacji problemów decyzyjnych (zbiorów rekurencyjnych) według względnej trudności. ”

Nie mogłem znaleźć kopii online ani w naszej bibliotece.

cc.complexity-theory reference-request ho.history-overview Kaveh
źródło
1
Tytuł jest interesujący, a praca doktorska powinna dać wgląd we wczesny rozwój pojęć, które uchwycą trudność funkcji obliczeniowych.
Mohammad Al-Turkistany
2
Mam nadzieję, że zachowają fizyczną kopię na Uniwersytecie Hebrajskim ...
Yuval Filmus
Komentarz niezwiązany (bezpośrednio) z PO: czy legalne jest gromadzenie internetowego repozytorium starych (nie wiem, jak długo kwalifikuje się jako stare) tez / rozpraw i umożliwić swobodny dostęp? Z wielu powodów nowsze są zazwyczaj łatwe do zdobycia.
Yixin Cao
Komentarze @YixinCao nie nadają się do zadawania nowych pytań stycznych. Możesz opublikować pytanie w witrynie Academia .
Kaveh
ps: okazuje się, że to nie teza Rabina. Jego praca magisterska według Wikipedii brzmi: „Rekurencyjna nierozwiązywalność grupowych problemów teoretycznych”, 1957.
Kaveh

Odpowiedzi:

14

W The National Library of Israel znajdują się dwa egzemplarze do wypożyczenia.

Oto zeskanowana kopia .

Yuval Filmus
źródło
1
Ładny. Czy to są wersje papierowe? Czy oferują wersję PDF?
Mohammad Al-Turkistany
2
Papierowe egzemplarze. Ale być może będą skanować je na żądanie. Prawdopodobnie sam mogę zdobyć fizyczną kopię, ale nie zamierzam skanować jej wszystkich sam ...
Yuval Filmus
3
Dzięki Yuval. Mam nadzieję, że ktoś ma zeskanowaną kopię (biorąc pod uwagę, że jest to jedno z podstawowych odniesień teorii złożoności).
Kaveh
@Kaveh: Czy to jedno z podstawowych założeń? Nigdy go nie cytowałem ... Mam skan „Matematycznej teorii automatów” Rabina, który jest jednym z trzech artykułów często cytowanych za wprowadzenie pojęcia P (i dlatego uważam je za fundamentalne). Daj mi znać, jeśli chcesz.
Joshua Grochow
@Josh, widziałem, że cytowano to wraz z Cobhamem i Edmondsem oraz Hartmanisem i Stearns jako pierwsze artykuły mówiące o tym, co obecnie nazywa się teorią złożoności obliczeniowej. Na szczęście Steve ma kopię rozprawy Rabina, powiedział, że zeskanuje ją i opublikuje online.
Kaveh