Gestalte GoConqr mit. Was sollen wir als Nächstes hinzufügen?

Mindmap

Máquinas de Turing e recursividade

Kykaze . Portugiesisch

Inhalt der Mindmap

Máquinas de Turing e recursividade

  1. O que é computável?

    • Alan Turing inicia seu artigo apresentando que irá estudar os números computáveis, explicando o que entende por um número Real computável. Turing faz isso por meio daquilo que chamou de "automatic machines". Uma máquina com uma fita onde se escreve e lê caracteres e uma memória finita (de estados). Apesar do nome de máquina, seu artigo define a máquina como um modelo matemático, portanto teórico.
    • Alonzo Church define uma linguagem que possui funções como cidadãos de primeira classe e que inspirou a criação da linguagem LISP na década de 1950 do século XX (MCCARTHY, 1960).
  2. Turing, assim como Church, provam que não existe um processo efetivo capaz de dada uma proposição matemática qualquer dizer se ela é verdadeira ou não. De fato, isso não foi surpresa, principalmente pelo fato de que em 1931, Kurt Gödel ter provado que existem enunciados sobre aritmética que são indecidíveis (GÖDEL, 1931), ou seja, que não podem ser demonstrados nem refutados

  3. Características das máquinas de Turing

    • O modelo de Turing para a computação, ou seja, a máquina de Turing tem um lugar central na história da computação (HAEUSLER, 2012). Turing é quem de fato demonstra matematicamente que é possível construir-se uma máquina programável.
    • Cada máquina de Turing realiza uma só tarefa. De início a máquina não era programável, fazendo com que Turing definisse a máquina universal, que executa outras máquinas de Turing.
    • Cada máquina de Turing aceita uma única linguagem, existe um mapeamento entre a máquina de Turing e a linguagem que ela aceita. Esse mapeamento não é injetivo, pois adicionando instruções inúteis, ou seja, que nunca serão executadas, pode-se definir uma quantidade infinita de máquinas de Turing que aceita a mesma linguagem.

Informationen

Beschreibung
Mindmap am Máquinas de Turing e recursividade, erstellt von Kykaze . am 13/11/2019.
Erstellt von
Kykaze .
Aufrufe
1
Bewertung

Mehr zu Máquinas de Turing

Feedback

Worum geht es?

Was sollen wir als Nächstes hinzufügen?