O “grau de dificuldade de Rabin em calcular uma função e uma ordem parcial de conjuntos recursivos”

Estou à procura de:

Michael O. Rabin, "Grau de dificuldade em calcular uma função e uma ordem parcial de conjuntos recursivos", Universidade Hebraica, Jerusalém, 1960

Resumo:

“Tentamos medir a quantidade de trabalho inerente à tarefa de calcular uma determinada função computável (recursiva). Uma noção de grau de dificuldade de computação é introduzida e estudada. A noção é invariável no sentido de que é independente dos computadores idealizados (Máquinas de Turing) usados para calcular as funções em questão. São feitas solicitações para a classificação de problemas de decisão solucionáveis (conjuntos recursivos) de acordo com a dificuldade relativa. ”

Não consegui encontrar uma cópia online ou em nossa biblioteca.

cc.complexity-theory reference-request ho.history-overview Kaveh
fonte

O título é interessante e a tese deve fornecer insights sobre o desenvolvimento inicial de noções que capturam a dureza das funções de computação.

Mohammad Al-Turkistany 03/04

Espero que manter uma cópia física na Universidade Hebraica ...

Yuval Filmus

Um comentário não (diretamente) relevante para o OP: é legal coletar um repositório on-line de teses / dissertações antigas (não sei há quanto tempo qualificadas como antigas) e permitir acesso gratuito? Por muitas razões, as mais recentes geralmente são fáceis de obter.

Yixin Cao 04/04

Os comentários do @YixinCao não são adequados para fazer novas perguntas tangenciais. Você pode postar uma pergunta no Academia .

Kaveh 04/04

ps: verifica-se que não é a tese de Rabin. Sua tese de acordo com a Wikipedia é "recursiva insolubilidade do teórico Problemas Grupo", 1957.

Kaveh

Respostas:

Existem duas cópias para empréstimo na Biblioteca Nacional de Israel.

Aqui está uma cópia digitalizada .

Yuval Filmus
fonte

Agradável. São cópias impressas? Eles oferecem versão em PDF?

Mohammad Al-Turkistany

Cópias impressas. Mas talvez eles os varram sob demanda. Eu provavelmente pode se apossar de uma cópia física mim, embora eu não estou indo para digitalizá-lo sozinho ...

Yuval Filmus

Obrigado Yuval. Espero que alguém tenha uma cópia digitalizada (considerando que é uma das referências fundamentais da teoria da complexidade).

Kaveh

@ Kaveh: É uma das referências fundadoras? Eu nunca o vi citado ... Eu tenho uma varredura da "Teoria Matemática dos Autômatos" de Rabin, que é um dos três trabalhos frequentemente citados por ter introduzido a noção de P (e que, portanto , considero fundamental). Deixe-me saber se você gostaria.

Joshua Grochow

@ Josh, eu já vi isso citado juntamente com os de Cobham e Edmonds e Hartmanis e Stearns como primeiros artigos falando sobre o que agora é chamado de teoria da complexidade computacional. Felizmente, Steve tem uma cópia da tese de Rabin, ele disse que irá digitalizar e publicar online.

Kaveh