Mostrando postagens com marcador Máquina de Turing. Mostrar todas as postagens
Mostrando postagens com marcador Máquina de Turing. Mostrar todas as postagens

segunda-feira, julho 14, 2008

1912 - 1954 - Alan Turing - Máquina de Turing - Teste de Turing


1) Introdução

Alan Mathison Turing nasceu em 23 de junho de 1912 em Londres, filho de um oficial britânico, Julius Mathison e Ethel Sara Turing. Seu interesse pela ciência começou cedo, logo que aprendeu a ler e escrever, distraia-se fatorando números de hinos religiosos e desenhando bicicletas anfíbias.

A maior parte do seu trabalho foi desenvolvido no serviço de espionagem, durante a II Grande Guerra, levando-o somente por volta de 1975 a ser reconhecido como um dos grandes pioneiros no campo da computação.

Em 1928, Alan começou a estudar a Teoria da Relatividade, conhecendo Christopher Morcom, que o influenciou profundamente. Morcom morreu em 1930 e Alan se motivou a fazer o que o amigo não teve tempo, durante anos trocou correspondências com a mãe de Morcom a respeito das idéias do amigo e se maravilhou com a possibilidade de resolver problemas com a teoria mecânica quântica. Chegou inclusive a escrever sobre a possibilidade do espirito sobreviver após a morte.

2) Turing Universal Machine

Depois de concluir o mestrado em King's College (1935) e receber o Smith's prize em 1936 com um trabalho sobre a Teoria das Probabilidades, Turing se enveredou pela área da computação. Sua preocupação era saber o que efetivamente a computação poderia fazer. As respostas vieram sob a forma teórica, de uma máquina conhecida como Turing Universal Machine, que possibilitava calcular qualquer número e função, de acôrdo com instruções apropriadas.

Quando a II Guerra Mundial eclodiu, Turing foi trabalhar no Departamento de Comunicações da Gran Bretanha (Government Code and Cypher School) em Buckinghamshire, com o intuito de quebrar o código das comunicações alemãs, produzido por um tipo de computador chamado Enigma. Este código era constantemente trocado, obrigando os inimigos a tentar decodifica-lo correndo contra o relógio. Turing e seus colegas cientistas trabalharam num sistema que foi chamado de Colossus, um enorme emaranhado de servo-motores e metal, considerado um precursor dos computadores digitais.


Durante a guerra, Turing foi enviado aos EUA a fim de estabelecer códigos seguros para comunicações transatlânticas entre os aliados. Supõe-se que foi em Princeton, NJ, que conheceu Von Neumann e daí ter participado no projeto do ENIAC na universidade da Pensilvânia..
Terminada a guerra, Alan se juntou ao National Physical Laboratory para desenvolver um computador totalmente inglês que seria chamado de ACE (automatic computing engine).Decepcionado com a demora da construção, Turing mudou-se para Manchester.


Em 1952, foi preso por "indecência", sendo obrigado a se submeter à pisicoanálise e a tratamentos que visavam curar sua homosexualidade. Turing suicidou-se em Manchester, no dia 7 de junho de 1954, durante uma crise de depressão, comendo uma maçã envenenada com cianureto de potássio.

3) Teste de Turing

O teste consistia em submeter um operador, fechado em uma sala, a descobrir se quem respondia suas perguntas, introduzidas através do teclado, era um outro homem ou uma máquina. Sua intenção era de descobrir se podiamos atribuir à máquina a noção de inteligência.


sexta-feira, dezembro 28, 2007

Gramática de Sânscrito

No século V a.C., na antiga Índia, o gramático Pānini formulou a gramática de Sânscrito usando 3959 regras conhecidas como Ashtadhyāyi, de forma bastante sistemática e técnica. Pānini usou meta-regras, tranformações e recursividade com tamanha sofisticação que sua gramática possuía o poder computacional teórico tal qual a Máquina de Turing.

quinta-feira, dezembro 27, 2007

Algoritmo

Algoritmo - Wikipédia

Aproximadamente em 825, o matemático persa Al-Khwarizmi escreveu o livro On the Calculation with Hindu Numerals, responsável pela difusão do sistema de numeração hindu-arábico no Oriente Médio, e posteriormente na Europa.

Por volta do século XII houve uma tradução do mesmo livro para o latim: Algoritmi de numero Indorum. Tais livros apresentaram novos conceitos para definir sequências de passos para completar tarefas, como aplicações de aritmética e álgebra. Por derivação do nome, atualmente usa-se o termo algoritmo.

Um algoritmo é uma sequência não ambígua de instruções que é executada até que determinada condição se verifique.

Mais especificamente, em matemática, constitui o conjunto de processos (e símbolos que os representam) para efectuar um cálculo.

O conceito de algoritmo é freqüentemente ilustrado pelo exemplo de uma receita, embora muitos algoritmos sejam mais complexos.

Eles podem repetir passos (fazer iterações) ou necessitar de decisões (tais como comparações ou lógica) até que a tarefa seja completada.

Um algoritmo corretamente executado não irá resolver um problema se estiver implementado incorretamente ou se não for apropriado ao problema.

Um algoritmo não representa, necessariamente, um programa de computador, e sim os passos necessários para realizar uma tarefa.

Sua implementação pode ser feita por um computador, por outro tipo de autômato ou mesmo por um ser humano.

Diferentes algoritmos podem realizar a mesma tarefa usando um conjunto diferenciado de instruções em mais ou menos tempo, espaço ou esforço do que outros. Tal diferença pode ser reflexo da complexidade computacional aplicada, que depende de estruturas de dados adequadas ao algoritmo.

Por exemplo, um algoritmo para se vestir pode especificar que você vista primeiro as meias e os sapatos antes de vestir a calça enquanto outro algoritmo especifica que você deve primeiro vestir a calça e depois as meias e os sapatos.

Fica claro que o primeiro algoritmo é mais difícil de executar que o segundo apesar de ambos levarem ao mesmo resultado.

O conceito de um algoritmo foi formalizado em 1936 pela Máquina de Turing de Alan Turing e pelo cálculo lambda de Alonzo Church, que formaram as primeiras fundações da Ciência da Computação.