Respostas do 1º capítulo de Teoria da Computação: máquinas universais e computabilidade.

exercício 1.1
RESPOSTA:

A origem do estudo da computação é milenar e se desenvolveu em diversas épocas e culturas, objetivando responder questões como:
■ O que é uma solução computável?
■ Quais são os limites do que pode ser computado?
■ Existem problemas sem solução computacional?
Foi a partir do século XX que importantes contribuições ocorreram, com destaque para os trabalhos de Hilbert (problema de decisão), de Church (cálculo Lambda e hipótese de
Church) e de Turing (máquina de Turing e problema da parada). Assim, o estudo da teoria da computação independe do estudo do computador (hardware e software) como se conhece hoje. Por outro lado, é uma base fundamental para qualquer estudo atual em ciência da computação. exercício 1.2
RESPOSTA:

Denominado de problema de decisão (também conhecido como Entscheidungsproblem), proposto como um dos desafios para o século XX e formalizado em 1928 como segue: encontrar um algoritmo que recebe como entrada a descrição de uma linguagem formal e uma sentença nesta linguagem e tem como saída “verdadeiro” ou “falso” dependendo se a sentença de entrada é verdadeira ou falsa.
Este problema é frequentemente identificado com o problema de decisão da lógica de primeira ordem (no qual a quantificação é restrita às variáveis que denotam elementos de conjuntos), ou seja, determinar algoritmicamente se uma sentença na lógica de primeira ordem é válida ou não. A procura de Hilbert por tal procedimento se justifica pelo fato de que ele acreditava que todo problema bem definido poderia ser resolvido. De fato, até 1930, ele acreditavaque não existia problema sem solução.
Entretanto, para responder o problema de decisão de Hilbert, era necessário formalizar a definição de algoritmo, o que foi feito em 1936 independentemente pelo matemático americano
Alonzo Church (1903~1995) e pelo matemático britânico Alan Turing (1912~1954).
Alonzo Church usou dois formalismos para mostrar que o problema de Hilbert não tem