Рабина «Степень сложности вычисления функции и частичное упорядочение рекурсивных множеств»

13

Я ищу:

  • Майкл О. Рабин, «Степень сложности вычисления функции и частичное упорядочение рекурсивных множеств», Еврейский университет, Иерусалим, 1960

Резюме:

«Мы пытаемся измерить объем работы, свойственный задаче вычисления заданной вычислимой (рекурсивной) функции. Представлено и изучено понятие степени сложности вычислений. Понятие инвариантно в том смысле, что оно не зависит от идеализированных компьютеров (машин Тьюринга), используемых для вычисления рассматриваемых функций. Применяются для классификации решаемых задач решения (рекурсивных множеств) по относительной сложности ».

Я не смог найти копию онлайн или в нашей библиотеке.

Кава
источник
1
Название интересное, и тезис должен дать представление о раннем развитии понятий, которые отражают сложность вычислительных функций.
Мухаммед Аль-Туркистани
2
Я надеюсь, что они хранят физическую копию в Еврейском университете ...
Yuval Filmus
Комментарий, не относящийся (непосредственно) к ФП: законно ли собирать онлайн-хранилище старых (я не знаю, сколько времени считается старым) тезисов / диссертаций и разрешать свободный доступ? По многим причинам, новые обычно легко получить.
Исинь Цао
Комментарии @YixinCao не подходят для того, чтобы задавать новые вопросы. Вы можете оставить вопрос по Академии .
Каве
PS: оказывается, это не тезис Рабина. Его диссертация по Википедии - «Рекурсивная неразрешимость групповых теоретических задач», 1957 г.
Каве,

Ответы:

14

Есть две ссудные копии в Национальной библиотеке Израиля.

Вот отсканированная копия .

Юваль Фильмус
источник
1
Ницца. Это печатные копии? Они предлагают версию PDF?
Мухаммед Аль-Туркистани
2
Жесткие копии. Но, возможно, они будут сканировать их по требованию. Я, вероятно, могу получить физическую копию самостоятельно, хотя я не собираюсь сканировать все это самостоятельно ...
Yuval Filmus
3
Спасибо, Юваль. Я надеюсь, что у кого-то есть отсканированная копия (учитывая, что это одна из основополагающих ссылок теории сложности).
Каве
@Kaveh: это одна из основополагающих ссылок? Я никогда не видел его привели ... У меня есть скан Рабин «Математическая теория автоматов» , которая является одним из трех работ часто цитируемых за то , что ввели понятие Р (и которые я поэтому делать рассмотреть основополагающим). Дай мне знать, если тебе понравится.
Джошуа Грохов
@ Джош, я видел, как это цитировалось вместе с Кобхэмом, Эдмондсом, Хартманисом и Стернсом как первые статьи, в которых говорится о том, что сейчас называется теорией вычислительной сложности. К счастью, у Стива есть копия тезиса Рабина, и он сказал, что отсканирует и разместит его в Интернете.
Каве