Tese de Church-Turing

Abstract

Esta monografia tem a modesta intenção de mostrar que é importante a definição formal de algoritmo, a qual levou a formulação da tese de Church-Turing. Esta é a base para a solução de muitos problemas que não tinham solução antes da definição matemática de algoritmo, Alonzo Church e Alan Turing foram os pioneiros nesta descoberta e podem ser chamados "pais" da ciência da computação. A tese de Church-Turing foi uma das grandes teses do mundo. Isto colocou que tudo que é possivel fazer com um rigoroso algoritmo (efetivo), pode ser feito por uma máquina de Turing. Este trabalho aborda os aspectos históricos e técnicos da tese de Church-Turing, levando o leitor à compreender, a importância desta tese, e da sua aplicabilidade.

The main objective of this work is to show how important is the formal definition of the term algorithm. It was the base for the solution of many problems with which had not solution before the advent of the mathematical definition of algorithm. Alonzo Church e Alan Turing were the pioneer of this discovery and can be called the "fathers" of computer science. The Church —Turing thesis is one of the great thesis of the world. It puts that all that is possible to do with a rigorous (effective on) algorithim is possible to do with Turing machine. This work treats with historical and tecnical aspects of Churh-Turing Thesis showing its importance and applicability.