Análise de Algoritmos e Teoria da Computabilidade

Mais Macros Z X Y 2 Z U1 X Y U2 2 Z V1 U1 U2 CHECK X Y Z 0 U1 X Y U2 0 U3 Z U2 V1 U1 U3 LOOP X Y U1 X Y LOOP U1 Z V1 CHECK V1 Condicionais IF THEN ELSE GOTO L1 END GOTO L2 IF X Y THEN GOTO L1 END LOOP X Y ELSE GOTO L2 END IF ε THEN 1 END ELSE 2 END LOOP V 2 END V ε V V LOOP V 1 END WHILE Y Y X Y 2 END WHILE Y Y X WHILE ε LOOP IF ε THEN Y X Y X X X 1 END WHILE X X 1 END GOTO LOOP END STOP GOTO STOP STOP STOP STOP PL estendida letra A B Z digito 0 1 9 nome letra expressao operacao expressao instrucao atribuicao GOTO nome STOP instrucao rotulada nome instrucao instrucao laco LOOP expressao nome LOOP expressao laco programa f im f im END nome END se entao programa f im se entao programa ELSE programa f im programa instrucao rotulada nome digito nome letra numeral digito numeral digito operacao atribuicao nome expressao expressao nome numeral expressao se entao IF expressao THEN nome IF EXPRESSAO THEN enquanto WHILE expressao nome WHILE EXPRESSAO enquanto programa f im programa programa PL GOTO WHILE letra A B Z digito 0 1 9 nome letra atribuicao nome 0 LOOP nome programa END WHILE nome programa END programa atribuicao nome digito nome letra nome nome 1 nome nome programa programa Tese de Church e o Problema da Indecidibilidade Conceitos Programas Definidos e Indefinidos é definido em se x1 xr x1 xr dom f Se computa a função f Wr Ws Senão é indefinido em x1 xr Algoritmo Se para e fixos pára em todos possíveis valores de entrada computando uma função total então é um algoritmo r s Seja f Wr Ws Função Efetivamente Computável Uma função é efetivamente computável se existe um procedimento efetivo ou programa que dado eventualmente pára com saída caso e nunca pára caso contrário f Wr Ws x1 xr Wr fx1 xr x1 xr dom f Conjunto Contável Um conjunto infinito S é contável se existe uma correspondência 11 entre S e os números naturais ℕ Um conjunto S infinito é contável se existe uma correspondência 11 entre S e o conjunto W Ou ℕ S a1 1 2 a2 a0 0 W2 1 2 0 Se S é contável existe uma enumeração a0 a1 a2 Um conjunto finito S é sempre contável Conjunto Efetivamente Enumerável S ser contável não significa necessariamente que seja possível efetivamente enumerar os elementos de S Ou seja não precisa existir um procedimento efetivo que gera membros de S sucessivamente de forma que cada membro de S é eventualmente gerado Ex Existe um procedimento efetivo para calcular todas as casas decimais de pi 31415926 Não existe procedimento efetivo para calcular todas as casas decimais da maioria dos números reais Apresentação é uma apresentação da função É uma definição efetiva de uma função Ou seja uma definição que dá um método efetivo de computar uma função g0 g1 Enumeração efetiva de funções 0 1 Enumeração efetiva de apresentações i gi Um programa PL é um exemplo de apresentação Tese de Church Tese de Church 1936 Dada uma função total ela é efetivamente computável se e somente se ela é Não pode ser provada É uma tese e não um Teorema Mas Existem evidências computável por uma máquina de Turing ou PLcomputável ou recursiva ou computável por um algoritmo de Markov formalismos Alonzo Church Tese de Church 1936 Dada uma função ela é PLcomputável se e somente se ela é efetivamente computável Generalização Alonzo Church