In accordance to DARI/Poli/UFRJ

Computation is associated to a problem solution realization, that is, a functional calculus based on algorithm. The theory of computation, a subsection from Computer Science and Mathematics, seeks for problems that are computed by a specific model of computation. The earlier researchers have proposed several of such models. One of those models, known as Turing machines, proposes the construction of a universal device, capable of operating a sequence of instructions and data written on an infinite length tape. This machine operates each time on one tape slot by using a read/write head, and thus executing a program. Another model is based on recursive functions constructed in order to directly operate numbers. It is an approach similar to Lambda Calculus. Moreover, there is another approach with deals with grammar rules operation over a character sequence, such as Markov chains and Post systems. All those formalisms are computationally power equivalent, that is, any computation made into one model can also be made into the other models. Additionally, all those proposed models are equivalent to electronic computers. In fact, it is believed that all theoretical formalizations of the algorithm concept have equivalent computational power of a Turing machine; this is the Church-Turing thesis. The Theory of Computation studies issues concerned to the possibility of performing certain computations on certain machines (or theoretical formalism).

Introduction to computation, Church thesis, sets, functions, relations, recursive function, alphabets, languages, formal systems, Post production systems, formal languages, grammars, logical propositions, propositional formal systems, automata, Turing machines, computability, solutionability.

Ontem, 10Abr24, foi divulgado o prêmio Turing. Novamente saiu para Teoria da Computação, desta vez o laureado é Avi Wigderson e seus esforços no estudo do papel da aleatoriedade em Computação. Nesta entrevista ele comenta de forma clara como a Teoria da Computação é importante no estágio atual de conhecimento que estamos. Simples, direto e cristalino.

This is a brief article from BBC on "Who was Kurt Gödel, the mathematician compared to Aristotle who hiked with Einstein".

During 2007, there was a final course project for Dutch Film Academy (Amsterdam) which produced a 24 minute film based on the last year of Kurt Gödel’s life. It is an art-film, not and documentary on such period. It intends to perform an stylized fashion of the incompleteness theorem. The history and the concept are are mixed up at that exhibition. The director Igor Kramer and his crew made an effort to understand Gödel’s mental state at that time. Now, after 10 years, the film free exhibition is free.