Loading presentation...

Present Remotely

Send the link below via email or IM

Copy

Present to your audience

Start remote presentation

  • Invited audience members will follow you as you navigate and present
  • People invited to a presentation do not need a Prezi account
  • This link expires 10 minutes after you close the presentation
  • A maximum of 30 users can follow your presentation
  • Learn more about this feature in our knowledge base article

Do you really want to delete this prezi?

Neither you, nor the coeditors you shared it with will be able to recover it again.

DeleteCancel

Make your likes visible on Facebook?

Connect your Facebook account to Prezi and let your likes appear on your timeline.
You can change this under Settings & Account at any time.

No, thanks

Turing

No description
by

Marina Andretta

on 29 September 2015

Comments (0)

Please log in to add your comment.

Report abuse

Transcript of Turing

Seminário de Coisas Legais
Computação: Turing revela tudo!
Vida e obra de
Alan Turing

Máquina de Turing
1912
1954
1940
Problema da Parada
Nasce, em Londres, Alan Mathison Turing
Época de muitas
descobertas e invenções
Em 1936, inventou a Máquina de Turing, um artefato teórico que é capaz de modelar a lógica de algoritmos.
Ele foi um matemático, lógico e cientista da computação.
Em 1952, condenado por "indecência", é obrigado a fazer castração química para evitar a prisão.
Fim precipitado
O que ela é?
O que ela faz?
Para que ela serve?
Qual é o problema?
Como resolvê-lo?
Referências
Wikipedia
Youtube
Google Imagens
www.turing.org.uk
http://ironphoenix.org/tril/tm/
http://www.cgl.uwaterloo.ca/~csk/halt/
Um alfabeto finito

Uma fita infinita

Uma cabeça de leitura/escrita

Um registrador de estados

Uma tabela de transição finita
Uma
tabela finita de instruções
que, dados o estado em que a Máquina se encontra e o símbolo que a Máquina está lendo na fita no momento, diz à Máquina para fazer os seguintes passos:
Uma Máquina de Turing é composta por:
Uma
fita
dividida em células, uma ao lado da outra.

Cada célula contém um símbolo do alfabeto.

Células que não foram escritas contém o
símbolo especial "branco".

Supõe-se que a fita possa ser arbitrariamente estendida para a esquerda e para a direita. Ou seja, a Máquina de Turing tem tanta fita quanto é necessário para realizar sua computação.
O
alfabeto
contém
um símbolo especial "branco"
(denotado por '_')
e um ou mais outros símbolos.
Uma
cabeça
que pode ler e escrever símbolos na fita.

A cabeça pode se mover uma célula para a esquerda ou a direita da fita.
Um
registrador de estados
,
que armaneza o estado em que a
Máquina de Turing se encontra.

O conjunto de estados possíveis é finito.

O registrador de estados começa em um estado inicial especial. Existe um conjunto de estados finais especiais.
A Máquina de Turing funciona como um computador que roda um só programa.
Apesar de sua simplicidade, uma Máquina de Turing pode ser adaptada para simular a lógica de qualquer algoritmo computacional.

A Máquina de Turing é um mecanismo abstrato para representar um computador, e não um modelo para construir um computador de fato.

Elas ajudam cientistas da computação a entender os limites da computação mecânica.
Uma Máquina de Turing pode ser simulada por outra Máquina de Turing, o que faz com que esta possa ser considerada como um computador.
Foi muito influente no desenvolvimento da Ciência da Computação, formalizando os conceitos de "algoritmo" e "computação" com as Máquinas de Turing.
Turing é considerado por muitos o pai da Ciência da Computação e da Inteligência Artificial.
Durante a II Guerra Mundial, Turing trabalhou para o "Government Code and Cypher School" (GC&CS), o centro de quebra de códigos britânico.
Depois da Guerra, ele trabalhou no National Physical Laboratory, onde desenhou o ACE, um dos primeiros computadores capazes de armazenar programas.
Em 1948, "inventou" a decomposição LU.
Em 1954, é encontrado morto por envenenamento por cianeto.
Em 2009, depois de uma campanha na internet, o Primeiro Ministro britânico pediu desculpas públicas em nome do governo britânico pela maneira como Turing foi tratado.
Em 2010, foi feito um pedido para que o governo britânico concedesse perdão a Turing. O pedido foi negado. Em 2012, foi feito um novo pedido, que aguarda aprovação.
Dada a descrição de um programa de computador arbitrário, decidir se o programa pára ou se roda para sempre.

Isso é equivalente ao problema de decidir se, dado um programa e uma entrada, o programa irá parar ou rodar para sempre.
1. Apagar ou escrever um símbolo na posição da fita que
está sob a cabeça;
2. Mover a cabeça para a esquerda, direita ou
permanecer na mesma posição;
3. Permanecer no mesmo estado em que está ou
mover para o novo estado.
Dizemos que a Máquina de Turing pára quando ela
atinge um estado final.
Em 1936, Alan Turing provou que um algoritmo geral para resolver o Problema da Parada para todos os possíveis pares programa-entrada não pode existir.
Esboço da prova
int

para
(
string

programa
,
string

entrada
) {

if
(
programa pára com entrada
)

return
(
1
);

else

return
(
0
);
}
O Problema da Parada
é indecidível em
Máquinas de Turing.
int

auto-para
(
string

programa
){

return
(
para
(
programa,programa
));
}
int

confuso
(
string

programa
)

{

if
(
auto-para
(
programa
)) {

while
(1) {}

return
(0);
}

else

return
(1);
}
Suponha que seja possível criar
o programa:
Defina, agora, os programas:
O que acontece se calculamos
confuso(confuso)?
Se
confuso(confuso)
não pára,
confuso(confuso)
pára!
Se
confuso(confuso)
pára,
confuso(confuso)
não pára!
Full transcript