Funções Computacionais e Linguagens de Programação

Exercício 7 12ω a0a1a2 ai 12 αi ai0ai1ai2 12ω α a0 a1 a2 aj 3 ajj 1 se ajj 2 2 se ajj 1 α0 a00 a01 a02 a03 α1 a10 a11 a12 a13 α2 a20 a21 a22 a23 α3 a30 a31 a32 a33 Diagonal de Cantor é contável Conjunto das Partes cdPℕ cd f ℕ 01 A Pℕ A ℕ 1 se ai A i ℕ 0 se ai A i ℕ χAai A Pℕ χA k ℕgai 0 se i k χAak 1 1 se i k χAak 0 cd f ℕ 01 ℵ0 cdPℕ ℵ0 χAai se i k Cardinalidade Revisão O conjunto dos programas em uma linguagem de programação é contável B O conjunto de todos os textos finitos produzidos por um alfabeto é contável A O conjunto das funções totais de em é contável C ℕ ℕ O conjunto das funções totais de em é contável D Wr Ws Existem funções que não podem ser computadas Sim Sim Não Não cd A ℵ0 B A cd B ℵ0 cd C ℵ1 ℵ0 cd cd cd cd Wr Ws ℕ ℵ0 D ℵ1 ℵ0 Sim Funções Especiais Identidade Projeção Zero Sucessor Subtração Própria Concatenação Reversa Característica ιx x π W W 0 ζ W 0 W ς W W x y x y x y 0 W2 W ρσ1 σk σk σ1 ρ0 0 ρxσ σ ρx 1 se x A 0 se x A χA Wr W χAx caso contrário se W2 W ι W W A Wr ρ W W πx ζ 0 ςx x 1 x y xy x 0 0 x x x y z x y z Uma Linguagem Algorítmica Cap 2 Walter Brainerd Computabilidade Funções Parciais Recursivas Linguagem de Programação PL Máquinas de Registradores Ilimitados Máquinas de Registrador Único Máquina de Turing Algoritmos Rotulados de Markov 2 1 3 4 5 6 Modelos teóricos que levaram a construção dos computadores reais PL Programming Language Sintaxe letra A B Z digito 0 1 9 nome letra atribuicao nome 0 instrucao atribuicao instrucao rotulada nome instrucao laco LOOP nome laco programa f im f im END programa programa programa instrucao rotulada nome digito nome letra nome nome 1 nome nome GOTO nome instrucao nome LOOP nome nome END PL Programming Language Semântica PL é livre de contexto Computa funções de em s podem ser Variáveis Sempre inicializadas com 0 Rótulos P desvio de fluxo através do comando Repete o por um número de vezes prédefinido Mesmo que a variável seja alterada não interfere na quantidade de vezes que o laço será executado Wr Ws nome GOTO LOOP nome programa END programa nome O que o programa calcula LOOP X X X 1 END X 2 X X X X ou Faça um programa para calcular Z 0 LOOP Y LOOP X Z Z 1 END END Z X Y