Isomorphism Theorem and Cryptology

Roberto Lins Carvalho; Flávio Luis Mello

doi:10.17648/enig.v1i1.17

Article Tools

Print this article

Indexing metadata

How to cite item

Email this article (Login required)

Email the author (Login required)

Font Size

Open Journal Systems

Language

User

Journal Help

About The Authors

Roberto Lins Carvalho
Witty Group leader for artificial intelligence and knowledge visualization fields

Roberto Lins de Carvalho did his PhD. on in- formatics at University of Toronto (1974), MSc. on informatics at Pontifical Catholic University of Rio de Janeiro - PUC Rio (1969), under graduation on telecommunication engineering at Military Engi- neering Institute - IME (1967) and under graduation military studies at Military Academy of Agulhas Negras - AMAN (1961). Lectured at Pontifical Catholic University of Rio de Janeiro, Campinas University, Fluminense Federal University, Aeronau- tics Technological Institute and Military Engineering Institute, where supervised several master dissertations and doctoral thesis on theorem proving, knowledge base systems and knowledge representation. Over fourteen years is the leader of Witty Group coaching artificial intelligence computer applications and is retired from Scientific Computing Brazilian National Laboratory - LNCC.

Flávio Luis Mello
Assistant Professor at Electronics and Computation Engineering Department from Polytechnic School at Federal University of Rio de Janeiro

Flávio Luis de Mello did his DSc. on theory of computation and image processing at the Federal University of Rio de Janeiro - UFRJ (2006), MSc. on computer graphics at Federal University of Rio de Janeiro - UFRJ (2003), under graduation on systems engineering at Military Engineering Institute - IME (1998). Developed command and control systems and implemented military messages interchange ap- plications during twelve years as Brazilian Army officer. Responsible for developing software appli- cations based on theorem proving, knowledge base systems and knowledge representation from Witty Group. Associate Professor at the Electronics and Computing Department (DEL) of Polytechnic School (Poli) at Federal University of Rio de Janeiro (UFRJ) since 2007.

Journal Content
Browse

Notifications

Isomorphism Theorem and Cryptology

Roberto Lins Carvalho, Flávio Luis Mello

Abstract

This paper presents a Theory of Computation study based on recursive functions computability and innovates by performing parallels to relevant themes of Cryptography. Hence, it is presented the Hennie’s notion of "abstract family of algorithms" (AFA, for short) according to the authors’ un- derstanding, and also more judicious theorems demonstrations, many times completely different from those ones available in literature. The main issue is the Isomorphism Theorem which supports the Church-Turing Thesis and provides a connection between Cryptology and Linguistics.

Keywords

Algorithm; Recursive functions; Church-Turing Thesis; Fixed point theorem; Recursion theorem; Isomorphism theorem

Full Text:

PDF (Português (Brasil))

References

Hartley Rogers Jr. Theory of Recursive Functions and Effective Com- putability, 1st ed, McGraw-Hill Book Company, 1967.

Roberto Lins de Carvalho. Máquinas, Programas e Algoritmos, 2a Escola de Computação, Campinas, Universidade Estadual de Campinas, 1981.

Yu I. Manin. A Course in Mathematical Logic, 1st ed, Graduate Texts in Mathematics 53, Springer-Verlag, 1977.

Claudia Maria Garcia Medeiros de Oliveira and Roberto Lins de Carvalho. Modelos de Computação e Sistemas Formais, 11a Escola de Computação, Rio de Janeiro, Universidade Federal do Rio de Janeiro, 1998.

Elliott Mendelson. Introduction to Mathematical Logic, 3rd ed, Cole Mathematics Series, The Wadsworth and Brooks, 1987.

Michael Sipser. Introduction to The Theory of Computation, 2rd ed, Course Technology Series, Thomson, 2006.

J. E. Hopcroft and J. D. Ullman. Introduction to Automata Theory, Language and Computation. USA, Addison-Wesley Publishing Company, 1979

Adam Young and Moti Yung. Malicious Cryptography: Exposing Cryp- tovirology, John Wiley and Sons Inc., 2004.

Nigel J. Cutland. Computability: An introduction to recursive function theory, Cambridge University Press, 1980.

Guillaume Bonfante and Matthieu Kaczmarek and Jean-Yves Marion. A Classification of Viruses through Recursion Theorems, CiE 2007, volume 4497 of Lecture Notes in Computer Science, 2007.

Steven Homer and Alan L. Selman. Computability and Complexity Theory, Texts in Computer Science, 2nd ed, Springer, 2011.

Alan M. Turing. The Undecidable, chapter On Computable Numbers with an Application to the Entscheidungsproblem, pages 115-151. Raven Press, New York, 1965.

R. J. Nelson. Introduction to Automata, John Wiley and Sons, Inc., USA, 1965.

Frederick C. Hennie. Introduction to Computability, Series in Computer Science and Information Processing, Addison-Wesley, Reading, Mas- sachusets, USA, 1977.

Walter S. Brainerd and Lawrence H. Landweber. Theory of Computation, John Wiley and Sons, 1974.

Michael Machtey and Paul Young. An Introduction to the General Theory of Algorithms, Theory of Computation Series, Elsevier North Holland Inc., 1978.

Michel Pêcheux. Análise Automática do Discurso, In: Por uma Análise Automática do Discurso, Editors: Françoise Gadet and Tony Hak, Editora Unicamp, 3.ed., 1997.

DOI: https://doi.org/10.17648/enig.v1i1.17