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

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

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

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

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

Oto zeskanowana kopia .

— Yuval Filmus
źródło

Ładny. Czy to są wersje papierowe? Czy oferują wersję PDF?

— Mohammad Al-Turkistany

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

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