[LFA] Questionario (Máquina de Turing)

Prévia do material em texto

MÁQUINA DE TURING:
O que é a hierarquia de Chomsky? Onde se enquadra a MT?
 É uma classificação de linguagens formais, possui 4 níveis, linguagens regulares, linguagens livres de contexto, linguagens sensíveis ao contexto e linguagens recursivamente enumeráveis que onde se enquadra a Máquina de Turing. Essa classificação depende de sua complexidade.
Defina o conceito formal de máquina de Turing = MT.
MT = (Q, Σ, Γ, δ, q0, B, F)
Q: Conjunto finito de estados do controle
Σ: Conjunto finito de símbolos de entrada
Γ: Conjunto finito de símbolos da fita
δ: Função de transição δ(q, X) = (p, Y, D)
 q é um estado, X um símbolo da fita;
 p é o novo estado, em Q;
 Y é o símbolo em Γ que substitui X;
 D é L ou R, esquerda ou direita, direção em que a cabeça se move depois da substituição;
q0: Estado inicial
B: Branco, símbolo que preenche a fita, exceto as células com a entrada
F: Conjunto de estados de aceitação ou finais
Qual a definição informal de uma MT? Quais os problemas desta definição?
Uma fita que é dividida em células, uma adjacente à outra. Cada célula contém um símbolo de algum alfabeto finito. O alfabeto contém um símbolo especial branco (aqui escrito como ¬) e um ou mais símbolos adicionais. Assume-se que a fita é arbitrariamente extensível para a esquerda e para a direita, isto é, a máquina de Turing possui tanta fita quanto é necessário para a computação. Assume-se também que células que ainda não foram escritas estão preenchidas com o símbolo branco.
Um cabeçote, que pode ler e escrever símbolos na fita e mover-se para a esquerda e para a direita.
Um registrador de estados, que armazena o estado da máquina de Turing. O número de estados diferentes é sempre finito e há um estado especial denominado estado inicial com o qual o registrador de estado é inicializado.
Uma tabela de ação (ou função de transição) que diz à máquina que símbolo escrever, como mover o cabeçote (para esquerda e para direita) e qual será seu novo estado, dados o símbolo que ele acabou de ler na fita e o estado em que se encontra. Se não houver entrada alguma na tabela para a combinação atual de símbolo e estado então a máquina para.
 Note que cada parte da máquina é finita; é sua quantidade de fita potencialmente ilimitada que dá uma quantidade ilimitada de espaço de armazenamento.
 É um dispositivo ideal que ler de uma fita infinita e escreve nessa fita se movendo em qualquer direção e parando após o processamento. 
Problema é a infinitude pois de alguma forma teria que ser dimensionado. Não associa tempo. Como só existe uma única cabeça de leitura o deslocamento dela pode gerar alguns problemas na hora da implementação, teria mais complexidade.
O que é uma MT Universal (MTU)? Qual a vantagem e cite algum exemplo.
 A máquina de Turing universal é uma máquina genérica capaz de ser programada podendo comportar-se como uma máquina especifica, permitindo assim solucionar qualquer problema passível de resolução por uma máquina de Turing. Ex: O Hardware de uma máquina, Linguagem de programação universal. A vantagem é que precisa de apenas uma MTU onde essa máquina entenderia todas as outras.
Quais as vantagens do modelo da MT em relação a AFD, AFN ou AP?
Realiza escrita, e é direcional.
Qual a diferença entre as MT geradora e reconhecedora? Que tipo de problemas tratam?
Geradora: Uma máquina é dita geradora quando dada uma entrada e passando pelas funções de transições gera uma saída compatível com a linguagem da máquina e resolve problemas de localização.
Reconhecedora: Uma máquina é dita reconhecedora quando dada uma entrada e passando pelas funções de transições ler toda a entrada e chega a um estado final e retorna TRUE ou FALSE e resolve problemas de decisão.
O que é o PROBLEMA da PARADA? Qual a importância disso para a computação?
Supõe-se que um MT sempre para quando se encontra em um estado de aceitação. Porém, nem sempre é possível exigir que uma MT pare mesmo quando não ocorre aceitação. 
Problema: Não determinar um estado de aceitação e de parada para um problema, determinar para uma dada entrada se o programa irá parar. Pode ser necessário tempo e espaço arbitrários para o programa parar.
Não existe nenhum algoritmo ou máquina que consiga garantir um estado final para qualquer problema que seja introduzido a ela. Não consegue dizer se para qualquer problema aquilo em alguma hora irá parar. Demonstração disso é a auto referência. A importância é que foi a primeira situação em que se concebeu algo que a MT era incapaz de resolver.
As mudanças de uma MT determinística como uso de múltiplas fitas, múltiplos controles, ampliam o poder da MT? Justifique a sua resposta.
Não, pois uma MT de várias fitas pode ser simulada por uma MT de uma fita.
Determine os tipos de problemas que podem ser resolvidos por uma MT.
Resolve qualquer problema computacional. Admitindo que existe uma instancia válida, pois se não existir e suas regras de transição não forem capaz de detectar isso, poderá chegar em um estado de inconsistência.
Faça um esboço de um pseudoalgoritmo para CODIFICAR uma MTU.
Receber as tuplas de definição formal da MT (estados, alfabeto da máquina, alfabeto da fita, estado inicial, transições, conjunto de estados finais...).
Realiza uma codificação intermediária com números decimais de acordo com a quantidade de símbolos em cada tupla e as separa com um símbolo separador determinado.
Receber a entrada.
Verifica se a entrada é composta por símbolos válidos do alfabeto da MT.
Aplica a codificação intermediária utilizada nas tuplas sobre a entrada.
Fazer o processamento da entrada de acordo com as transições da MT, se chegar a um estado final valido (através do HALT) obtém-se a saída.
Aplica a codificação intermediária utilizada nas tuplas sobre a saída.
 Realiza a codificação binária em toda a fita.
COMPUTABILIDADE:
Explique o conceito de conjuntos enumeráveis e qual a sua importância para MT.
Conjuntos enumeráveis são conjuntos finitos contáveis ou infinitos, porém ainda assim contáveis
As Máquinas de Turing são números, são expressadas por um número que representa um código e este precisa ser contável 
Cada elemento do conjunto tem um código, tem um número associado, um significado. A importância para a MT é que se eu vou codificar e tudo recebe um código, significa que a própria MT é um código. Ou seja, esses números me levam a MT.
O que é uma linguagem recursiva? E recursivamente enumerável? Qual a relação entre MT e tais linguagens?
Recursiva: Tem um passo indutivo e a partir dele qualquer coisa está bem-comportada dentro do meu domínio. Sempre consegue dizer sim ou não. Que são os problemas decidíeis.
Uma linguagem diz-se recursiva ou definível se existe uma máquina de Turing que a reconhece, isto é, a máquina para para todos os dados e : num estado final se a palavra dada pertence a linguagem , num estado final se a palavra dada não pertence a linguagem
Recursivamente enumerável: É aquele que consegue dizer “SIM” mas não consegue dizer “NÃO”. E para as que são reconhecidas recebem uma numeração. Que são os problemas semi decidível. 
Uma linguagem diz-se recursivamente enumerável ou semi-decidível se é aceita por uma máquina de Turing.
Como conjuntos incontáveis podem ser usados para analisar problemas que não podem ser computáveis?
Um problema é não computável se não houver uma máquina de Turing que possa resolvê-lo, visto que Máquinas de Turing reconhecem linguagens enumeráveis e são representadas por um código de números de conjuntos enumeráveis, seja finito ou infinito, porém contável, então conjuntos incontáveis, funções incontáveis não são computáveis, como a diagonal de Cantor. 
Existem em conjuntos incontáveis infinitos conjuntos não computáveis, como a diagonal de Cantor. 
Qual o objetivo da INCOMPLETUDE da aritmética e as implicações para a computação?
A aritmética não está completa porque tem coisas nela que não podem ser demostráveis nela. Implica na computação pois como a aritmética trata de números,e as MTs são mapeadas baseadas em operações sobre os números naturais. Se existe um limite em um universo maior que a MT, então MT também estará limitada, então a incompletude impede que a MT possa ter condições de falar sobre qualquer coisa.
O que é a Tese de Church-Turing? Qual a vantagem desta abordagem? Qual o problema com esta tese?
“A capacidade de computação representada pela Máquina de Turing é o limite máximo que pode ser atingido por qualquer dispositivo de computação”
A hipótese não é demonstrável, um algoritmo ou função computável não é matematicamente preciso. Não há como definir o conjunto de todas as máquinas possíveis.
A tese fala que o que uma máquina consegue fazer, uma função matemática poderia fazer. As MT executam funções e traz o mundo do modelo para o mundo da aritmética. Limite é que é só conceitual nada foi provada.
A tese de Church-Turing baseia-se na ideia de equivalência entre as funções lambda e a Máquina de turing. O problema é que essa tese não foi provada.
Por que se pode considerar o modelo de Turing como limite para a computação? Dê razões para isso.
Segundo a hierarquia de Chomsky o L0 é coberto por MT e não existe uma linguagem além de L0. 
As MT podem dar resultado “SIM/NÃO” ou pode dar resultado “SIM”. Isso também é um limite pois a outra possibilidade seria o “NÃO”. 
PROBLEMAS:
Defina o conceito de um problema não computável e exemplifique.
É um problema que não existe uma MT capaz de resolver.
Ex: O problema da parada, os elementos da diagonal de Cantor como um elemento que não está em lugar nenhum.
Defina o conceito de um problema intratável e exemplifique.
 É um problema solúvel, mas demanda um tempo de processamento muito alto. Ex: Qualquer problema computável que seja exponencial.
Explique e exemplifique os conceitos de decidibilidade, computabilidade e complexidade.
Decidibilidade: Reconhece ou não, problema de decisão, a questão da existência de um método efetivo para determinar a pertinência em um conjunto de fórmulas.
Computabilidade: Consegue computar ou não algo? Tá ou n preso a uma Mt.
É a habilidade de resolver problemas de forma efetiva. É um tópico chave para o campo da Teoria da Computabilidade dentro da Lógica Matemática e para a Teoria da Computação dentro da Ciência da Computação.
Complexidade: Lida com oq é tratável ou intratável.
Complexidade computacional. A teoria da complexidade computacional é um ramo da teoria da computação em ciência da computação teórica e matemática que se concentra em classificar problemas computacionais de acordo com sua dificuldade inerente, e relacionar essas classes entre si.
O que é a função de redução entre problemas? Por que isso é útil?
Tem um problema p1 e transforma em p2. 
Visto a complexidade de um problema p1 reduz-se o problema em p1 para p2 de maneira a diminuir sua complexidade, se p2 for solúvel então p1 tbm será.
Pode ser útil para a resolução de problemas e determinar sua solubilidade. 
Determine o que é um problema da categoria “P”. Diga o que é um problema NP e um NP-Completo e qual a importância deste último.
O problema P é um problema que é solucionável em tempo polinomial. 
Problemas P são problemas solucionáveis em tempo polinomial, de forma que exista um algoritmo polinomial (dada uma instância de um problema, informa a solução ou que não é solucionável)
O problema NP ele não conseguiu uma solução em uma MT não determinística.
São problemas polinomialmente verificáveis, dada uma instância de um problema e uma suposta solução informa se é a solução do problema 
O problema NP-Completo é o conjunto dos NP que são alto reduzíveis
Um problema é NP-Completo se for NP-difícil e estiver em NP, um problema X é NP-difícil se todos os problemas em NP não são mais difíceis que X.
Qual a implicação de P = NP?
Transformar o que é exponencial em polinomial.
Problemas exponenciais podem se tornar polinomiais e podem ser resolvidos por algoritmos polinomiais.
O que é o SAT? Qual a importância deste problema? [Josinaldo Batista]
É o menor no conjunto de NP-completo, se ele é o mais simples, se for resolvido e transformado em polinomial todos os outros também poderão ser resolvidos.
Qual a relação entre problemas e problemas computáveis?
Existe muito mais problemas do que problemas computáveis.
O que falar da cardinalidade entre problemas solúveis e insolúveis?
O infinito dos problemas insolúveis é bem maior do que o infinito dos problemas solúveis.
Qual a diferença entre problemas intratáveis e problemas não computáveis?
Problemas intratáveis são problemas computáveis, mas que são exponenciais, ou seja, pode levar um tempo arbitrário para ser resolvido, diferente dos problemas não computáveis que mesmo dando todo o tempo possível não é capaz de ser reconhecido.
Explique por que nem todos os problemas podem ser solucionáveis.
Tem a ver com o problema da parada, auto referência.
Na ideia dos “7C”, explique o que significa um algoritmo ser:
Completo, Consistente, Correto
Completo: Quando observou todos os elementos do universo.
Consistente: Independentemente da quantidade de vezes que for computado sempre resultará na mesmo coisa.
Correto: Garante que a resposta é a correta.
Compacto, Contido, Canônico
Compacto: É pequeno tem uma estrutura pequena.
Contido: Tem a ver com os recursos usados na execução, tem que ser o menor possível.
Canônico: Tem um padrão.
Católico
Católico: É que qualquer programa computável pode ser usado na mesma estrutura.
TENDÊNCIAS: 
Na sua visão, o que é necessário para superar o modelo de Turing?
Mostrar uma solução para o problema da parada, tratar a auto referência
Mapear, transformar problemas semidecidíveis em recidiveis por exemplo.
Nos autômatos não determinísticos o não determinismo pode ser simulado no determinismo (isso é uma característica do modelo), mas na natureza é assim que funciona? Por trás do não determinismo da natureza existe um determinismo?
Pode ser que se demonstre que existe um poder computacional não determinístico que não é reduzível ao determinístico.
Quais os impactos de uma eventual demonstração de que a tese Church-Turing é falsa?
Isso significa que ou a máquina de Turing tem mais poder do que pensávamos ou ela tem menos poder. Ou seja, existiriam operações de cálculo que computacionalmente não seriam possíveis nesse cenário, no outro cenário existiriam operações computacionais que não conseguem ser traduzidas em operações de cálculo. Essa divergência faria com que possivelmente o conceito de software precisasse ser mudado, já que o software representa uma máquina de Turing teria que ter algum tipo de adaptação para cobrir esses outros cenários com essa limitação.
 
Em que as singularidades podem representar impactos para o modelo de Turing?	
Singularidade: a partir de um certo ponto não existe a clara compreensão
Imaginamos conhecer o que a máquina de Turing faz, modelo que define as transições, ou uma função e etc. Se existe uma singularidade e eu não sei o q ela faz pode ser uma limitação minha ou do modelo, eu não fui ainda capaz de traduzir isso em uma máquina de Turing
Utilizando uma máquina de Turing Universal realiza uma tentativa de resolver o que acontece na singularidade, se n for possível de forma alguma é uma limitação minha ou do modelo? Isso não está resolvido.
O problema das singularidades é que como elas colocam um véu em cima do que eu posso ver, do que eu consigo fazer, do que eu consigo ver o que a MT produziria, eu fico limitado e essa limitação ainda não é visível.
Se singularidades tecnológicas ocorrerem, qual o papel da humanidade nisso?
Culpa pela singularidade, criação das máquinas
A humanidade passa a ter um papel ativo conflitante em relação as máquinas, visto que historicamente convergir não é o comum.
Irracionalidade humana difere das máquinas independente da singularidade.
Do ponto de vista evolutivo quem vence é o mais adaptável e o mais adaptável não é o racional.
DEMONSTRAÇÕES: 
Codifique uma máquina de Turing de maneira compacta;Codifique uma MTU com suas entradas e saídas usando apenas binário.
 
Que tipos de regras podem ser usadas para avaliar se uma MTU está correta?
HALT não está em um estado final, as transições não tem símbolos do alfabeto ou da fita, um estado que não me leva a um estado final
Faça uma máquina de Turing para determinar se um número binário é múltiplo de 4.
Caderno
 
Projete uma MT para dar o resto da divisão de um número por 4.
Caderno
AUTOMATO CELULAR:
O que é um CA (Cellular Automata)
As regras são estruturais, existe uma estrutura que é a célula, ela analisa tempos anteriores e ela é simples porque é binária, o alfabeto é binário, isso significa que um autômato celular, as regras dele em geral são extremamente simples em relação a MT
Qual a característica / vantagem desse modelo?
A vantagem é a simplicidade
Qual a visão de aplicação deste modelo?
Tem sido estudado extensivamente nas áreas: ciência natural, matemática, ciência da computação. São usados como modelo de fenômenos físicos e biológicos tais como: fluxo de fluído, formação de galáxias, terremotos, formação padrão biológico. 
O que são CA unidimensional?
Apenas dois vizinhos, codifica os dois vizinhos juntamente e verifica ativado ou não [olhar no slide]
Uma linha de células. Partindo d uma linha inicial de células, evolui-se em passos de tempo de acordo com regras criando novas linhas abaixo da anterior. Uma célula e as suas duas vizinhas (da direita e da esquerda) formam uma vizinhança de 3 células, por isso existem 2^3 = 8 padrões possíveis para uma vizinhança. Há então 2^8 = 256 regras diferentes possíveis.
Exemplifique um REGRA de um CA unidimensional.
 O autômato-celular é dividido em oito células, cada célula pode carregar 0 ou 1 e os valores decimais que as células representam em binário variam de 0 a 7 da esquerda para direita.
Defina com suas palavras o que é uma regra “sustentável”?
Universo sustentável, ideia de vida e morte, nem todo mundo vivo e nem todo mundo morto
Como um CA bidimensional pode ser pensado? Quais as suas complexidades?
Modelo de cruz de von Neuman, ou o modelo de quadrado completo com oito vizinhos (The Moore)
O que é o Jogo da Vida (Game of Life = GL)? Por que é importante?
É um autômato celular bidimensional, cuja regras simulam comportamentos dos seres
Quais as características de uma célula no GL? E qual a importância da coletividade?
Sua importância é a ideia de um autômato reproduzir a natureza
Qual o conceito de “vida” artificial neste sentido?
Modelo sustentável, oscilações na população, gera um padrão
Morte: Se a contagem das células vivas (on, 1) for menor que dois (2) ou maior que três (3) a célula corrente é então trocada para situação de morte (off, 0).
Sobrevivência: a) Se a contagem é exatamente 2;ou b) A contagem é exatamente 3 e a célula corrente está em on, a célula corrente não é alterada. 
Nascimento: Se a célula corrente está em off e a contagem é exatamente 3, a célula corrente é trocada para on (1).
EPSTEMOLOGIA COMPUTACIONAL:
Como novos modelos computacionais podem revolucionar a civilização?
Novos modelos computacionais podem ser resultado de outras mudanças visto que os modelos computacionais existentes se baseiam em uma série de ideias que são reflexo da natureza, da matemática e do comportamento e evolução humana.
É possível realmente gerar complexidade e comportamentos emergentes a partir de entidades simples? Qual a sua visão?
Tese do Wolfram
Segundo Wolfram a complexidade é uma série de problemas simples.
[Pesquisar]
Em que aspecto uma IA fraca existe em autômatos?
IA fraca -> o programador dá a lógica, simulação de inteligência a partir de regras interessantes.
Trata-se da noção de como lidar com problemas não determinísticos.
Uma contribuição prática de Alan Turing foi o que se chamou depois de Teste de Turing (TT), de 1950: em lugar de responder à pergunta “podem-se ter computadores inteligentes?” ele formulou seu teste, que se tornou praticamente o ponto de partida da pesquisa em Inteligência Artificial”. A inteligência artificial fraca centra a sua investigação na criação de inteligência artificial que não é capaz de verdadeiramente raciocinar e resolver problemas. Uma tal máquina com esta característica de inteligência agiria como se fosse inteligente, mas não tem autoconsciência ou noção de si. O teste clássico para aferição da inteligência em máquinas é o Teste de Turing.
Como a IA forte vê o progresso da tecnologia?
Precisa de um momento em que surgiu algo que não é fruto da sua instrução original, comportamento emergente.
A investigação em Inteligência Artificial Forte aborda a criação da forma de inteligência baseada em computador que consiga racionar e resolver problemas uma forma de IA forte é classificada como autoconsciente. A IA forte é tema bastante controverso, pois envolve temas como consciência e fortes problemas éticos ligados ao que fazer com uma entidade que seja cognitivamente indiferenciável de seres humanos.
Até que ponto a computação reflete o universo? Como explicar isso?
 
O que é uma singularidade tecnológica? Isso é bom ou ruim?
 
Qual a relação entre criatura e criador no contexto de inteligência?
 
Explique a relação entre ciência e teologia e como isso pode ser abalado (ou não) na ótica da computação. 
A religião e a ciência se completam no sentido de tentarem trazer resposta que em algum ponto uma delas falha, mas conflitam em pontos convergentes, a teologia em uma questão de fé e a ciência em um campo lógico, a computação traz aspectos da matemática, da física e da biologia, de forma que a ciência é uma ferramenta de grande importância, mas tbm há aspectos “sombrios” que parecem não ter outra explicação a não ser teológica.
Qual o futuro da computação? E qual o papel dos analistas e desenvolvedores neste futuro?