Logotipo
Unionpédia
Comunicação
Disponível no Google Play
Novo! Faça o download do Unionpédia em seu dispositivo Android™!
Faça o download
Acesso mais rápido do que o navegador!
 

Máquina de Turing

Índice Máquina de Turing

Representação artística de uma máquina de Turing A Máquina de Turing é um dispositivo teórico conhecido como máquina universal, que foi concebido pelo matemático britânico Alan Turing (1912-1954), muitos anos antes de existirem os modernos computadores digitais (o artigo de referência foi publicado em 1936).

61 relações: Alan Turing, Alemanha, Algoritmo, Algoritmo do castor, Alonzo Church, Argumento de diagonalização de Cantor, Autômato finito determinístico, Autômato linearmente limitado, Brainfuck, Cálculo lambda, Ciência da computação, Completude (lógica), Complexidade computacional, Computador, Consistência lógica, David Hilbert, Decidibilidade, Doodle, EDVAC, Emil Post, Entscheidungsproblem, Enupla, Equação diofantina, Ficção científica, Formiga de Langton, Função computável, Função parcial, George Stibitz, Google, Google Busca, Hao Wang (acadêmico), Howard Aiken, Inteligência artificial, Konrad Zuse, Kurt Gödel, Leonardo Torres y Quevedo, Martin Davis, Marvin Minsky, Maurice d'Ocagne, Max Newman, Máquina abstrata, Máquina de Post-Turing, Máquina de Turing não determinística, Máquina de Turing universal, Método efetivo, Número de Gödel, Paul Strathern, Problemas de Hilbert, Robin Gandy, Segunda Guerra Mundial, ..., Stephen Kleene, Teoria da computação, Tese de Church-Turing, Teste de Turing, Universidade de Heidelberg, Vannevar Bush, 1912, 1936, 1954, 1986, 23 de junho. Expandir índice (11 mais) »

Alan Turing

Alan Mathison Turing OBE (Paddington, Londres, — Cheshire East, Cheshire) foi um matemático, lógico, criptoanalista e cientista da computação britânico.

Novo!!: Máquina de Turing e Alan Turing · Veja mais »

Alemanha

Alemanha (Deutschland), oficialmente República Federal da Alemanha (Bundesrepublik Deutschland, 10px ouça), é um país localizado na Europa Central. É limitado a norte pelo mar do Norte, Dinamarca e pelo mar Báltico, a leste pela Polônia e pela República Checa, a sul pela Áustria e pela Suíça e a oeste pela França, Luxemburgo, Bélgica e Países Baixos. O território da Alemanha abrange 357 021 quilômetros quadrados e é influenciado por um clima temperado sazonal. Com 82,2 milhões de habitantes em 31 de dezembro de 2015, o país tem a maior população da União Europeia e é também o lar da terceira maior população de migrantes internacionais em todo o mundo. A região chamada Germânia, habitada por vários povos germânicos, foi conhecida e documentada pelos romanos antes do ano 100. A partir do, os territórios alemães formaram a parte central do Sacro Império Romano-Germânico, que durou até 1806. Durante o, o norte da Alemanha tornou-se o centro da Reforma Protestante. Como um moderno Estado-nação, o país foi unificado pela primeira vez em consequência da Guerra Franco-Prussiana em 1871. Em 1949, após a Segunda Guerra Mundial, a Alemanha foi dividida em dois estados, a Alemanha Ocidental, oficialmente "República Federal da Alemanha", e a "Alemanha Oriental", oficialmente República Democrática Alemã, ao longo das linhas de ocupação aliadas. A Alemanha foi reunificada em 1990. A Alemanha Ocidental foi um dos membros fundadores da Comunidade Europeia (CE), em 1957, que posteriormente se tornou na União Europeia, em 1993. O país é parte do espaço Schengen e passou a adotar a moeda europeia, o euro, desde quando foi instituído, em 1999. A Alemanha é uma república parlamentar federal de dezesseis estados (em alemão Länder). A capital e maior cidade do país é Berlim, localizada no nordeste do território alemão. O país é membro das Nações Unidas, da OTAN, G8, G20, da OCDE e da OMC. É uma grande potência com a quarta maior economia do mundo por PIB nominal e a quinta maior em paridade do poder de compra. É o segundo maior exportador e o segundo maior importador de mercadorias. Em termos absolutos, a Alemanha atribui o segundo maior orçamento anual de ajudas ao desenvolvimento no mundo, enquanto está em sexto lugar em despesas militares. O país tem desenvolvido um alto padrão de vida e estabeleceu um sistema global de segurança social. A Alemanha ocupa uma posição-chave nos assuntos europeus e mantém uma série de parcerias estreitas em um nível global. O país também é reconhecido como líder científico e tecnológico em vários domínios.

Novo!!: Máquina de Turing e Alemanha · Veja mais »

Algoritmo

Uma animação do algoritmo de ordenação quicksort de uma matriz de valores ao acaso. As barras vermelhas marcam o elemento pivô. No início da animação, estando o elemento para o lado direito, é escolhido como o pivô. Algoritmo é uma sequência finita de instruções bem definidas e não ambíguas, cada uma das quais devendo ser executadas mecânica ou eletronicamente em um intervalo de tempo finito e com uma quantidade de esforço finita.

Novo!!: Máquina de Turing e Algoritmo · Veja mais »

Algoritmo do castor

Em Teoria da Computação, o algoritmo do castor (busy beaver) é uma máquina de Turing que, após iniciada em uma fita vazia (todas as posições em branco ou com 0), executa o maior número de passos possível, mas eventualmente para.

Novo!!: Máquina de Turing e Algoritmo do castor · Veja mais »

Alonzo Church

Alonzo Church (Washington, DC, 14 de junho de 1903 — Hudson (Ohio), 8 de novembro de 1995) foi um matemático estadunidense.

Novo!!: Máquina de Turing e Alonzo Church · Veja mais »

Argumento de diagonalização de Cantor

Uma ilustração do argumento da diagonalização de Cantor (na base 2) para a existência de conjuntos incontáveis. A sequência na parte inferior não pode ocorrer em nenhum lugar na enumeração das sequências anteriores. Um conjunto infinito pode ter a mesma cardinalidade como um subconjunto de si próprio, como a representada bijeção ''f''(''x'').

Novo!!: Máquina de Turing e Argumento de diagonalização de Cantor · Veja mais »

Autômato finito determinístico

Um exemplo de autômato finito determinístico que aceita apenas números binários múltiplos de 3. O estado ''S''0 é tanto o estado de início quanto um estado de aceitação. Na Teoria dos autômatos, um sub-tópico da Ciência da computação teórica, um autômato finito determinístico — também chamado máquina de estados finita determinística (AFD) — é uma Máquina de estados finita que aceita ou rejeita cadeias de símbolos gerando um único ramo de computação para cada cadeia de entrada.

Novo!!: Máquina de Turing e Autômato finito determinístico · Veja mais »

Autômato linearmente limitado

Um Autômato linearmente limitado é uma Máquina de Turing com memória limitada e é o mecanismo reconhecedor de Linguagens sensíveis ao contexto.

Novo!!: Máquina de Turing e Autômato linearmente limitado · Veja mais »

Brainfuck

brainfuck, também conhecido como brainf*ck ou BF, é uma linguagem de programação esotérica notada pelo seu extremo minimalismo, criada por Urban Müller, em 1993.

Novo!!: Máquina de Turing e Brainfuck · Veja mais »

Cálculo lambda

Na lógica matemática e na ciência da computação, lambda cálculo, também escrito como cálculo-λ é um sistema formal que estuda funções recursivas computáveis, no que se refere a teoria da computabilidade, e fenômenos relacionados, como variáveis ligadas e substituição.

Novo!!: Máquina de Turing e Cálculo lambda · Veja mais »

Ciência da computação

A Ciência da Computação lida com fundamentos teóricos da informação, computação, e técnicas práticas para suas implementações e aplicações.

Novo!!: Máquina de Turing e Ciência da computação · Veja mais »

Completude (lógica)

Em lógica matemática e na metalógica, um sistema formal é chamado completo com respeito a uma propriedade específica se toda fórmula tendo a propriedade pode ser obtida usando esse sistema, isto é, é um de seus teoremas; caso contrário, o sistema é dito incompleto.

Novo!!: Máquina de Turing e Completude (lógica) · Veja mais »

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.

Novo!!: Máquina de Turing e Complexidade computacional · Veja mais »

Computador

Um assistente pessoal digital. Um computador pessoal. Columbia, um supercomputador da NASA. Computador é uma máquina capaz de variados tipos de tratamento automático de informações ou processamento de dados.

Novo!!: Máquina de Turing e Computador · Veja mais »

Consistência lógica

Na lógica uma teoria consistente é uma que não contenha uma contradição.

Novo!!: Máquina de Turing e Consistência lógica · Veja mais »

David Hilbert

David Hilbert (Königsberg, — Göttingen) foi um matemático alemão.

Novo!!: Máquina de Turing e David Hilbert · Veja mais »

Decidibilidade

Em lógica, o termo decidível se refere a um problema de decisão, ou seja, a questão da existência de um método efetivo para determinar a pertinência em um conjunto de fórmulas.

Novo!!: Máquina de Turing e Decidibilidade · Veja mais »

Doodle

''Doodle'' feito pela Rainha da Prússia, Luísa de Mecklemburgo-Strelitz, c. 1795 Doodle é uma palavra inglesa para referir um tipo de esboço ou desenho realizado ao acaso, quando uma pessoa está distraída ou ocupada.

Novo!!: Máquina de Turing e Doodle · Veja mais »

EDVAC

O EDVAC, instalado no Edifício 328 do ''Ballistics Research Laboratory''. EDVAC (Electronic Discrete Variable Automatic Computer) foi um dos primeiros computadores eletrônicos.

Novo!!: Máquina de Turing e EDVAC · Veja mais »

Emil Post

Emil Leon Post, nascido em 11 de fevereiro de 1897 em Augustów, no Império Russo (atual Polônia) e falecido em 21 de abril de 1954 em Nova York, Estados Unidos.

Novo!!: Máquina de Turing e Emil Post · Veja mais »

Entscheidungsproblem

O Entscheidungsproblem (termo alemão para "problema de decisão") é um problema da lógica simbólica que consiste em achar um algoritmo genérico para determinar se um dado enunciado da lógica de primeira ordem pode ser provado.

Novo!!: Máquina de Turing e Entscheidungsproblem · Veja mais »

Enupla

Uma enupla (também conhecida como n-tuplo, n-upla ou simplesmente tupla) é uma sequência ordenada de n elementos, que pode ser definida pela recursão do par ordenado.

Novo!!: Máquina de Turing e Enupla · Veja mais »

Equação diofantina

Na matemática, uma equação Diofantina é uma equação polinomial que permite a duas ou mais variáveis assumirem apenas valores inteiros.

Novo!!: Máquina de Turing e Equação diofantina · Veja mais »

Ficção científica

Ficção científica (normalmente abreviado para SF, FC, sci-fi ou scifi) é um gênero da ficção especulativa, que normalmente lida com conceitos ficcionais e imaginativos, relacionados ao futuro, ciência e tecnologia, e seus impactos e/ou consequências em uma determinada sociedade ou em seus indivíduos, desenvolvido no século XIX. Conhecida também como a "literatura das ideias", evita utilizar-se do sobrenatural, tema mais recorrente na Fantasia, baseando-se em fatos científicos e reais para compor enredos ficcionais. A ação pode girar em torno de um grande leque de possibilidades como: viagem espacial, viagem no tempo, viagem mais rápida que a luz, universos paralelos, mudanças climáticas, totalitarismo e/ou vida extraterrestre.

Novo!!: Máquina de Turing e Ficção científica · Veja mais »

Formiga de Langton

Formiga de Langton (do inglês, Langton's Ant) é uma Máquina de Turing bidimensional com um conjunto muito simples de regras, mas um complexo comportamento emergente.

Novo!!: Máquina de Turing e Formiga de Langton · Veja mais »

Função computável

Funções computáveis são os objetos básicos de estudo na teoria da computabilidade.

Novo!!: Máquina de Turing e Função computável · Veja mais »

Função parcial

Em matemática, uma função parcial é quase uma função, falhando na definição, porque para nem todos x do domínio existe algum f(x).

Novo!!: Máquina de Turing e Função parcial · Veja mais »

George Stibitz

George Stibitz (York (Pensilvânia), — Hanover) foi um engenheiro eletrônico e inventor estadunidense.

Novo!!: Máquina de Turing e George Stibitz · Veja mais »

Google

Google LLC (Google, pronuncia-se) é uma empresa multinacional de serviços online e software dos Estados Unidos.

Novo!!: Máquina de Turing e Google · Veja mais »

Google Busca

O Google Busca é um serviço da empresa Google onde é possível fazer pesquisas na internet sobre qualquer tipo de assunto ou conteúdo.

Novo!!: Máquina de Turing e Google Busca · Veja mais »

Hao Wang (acadêmico)

Wang Hao, também conhecido por Hao Wang, (Chinês: 王浩, —) foi um matemático e filósofo sino-americano.

Novo!!: Máquina de Turing e Hao Wang (acadêmico) · Veja mais »

Howard Aiken

Howard Hathaway Aiken (Nova Jérsei, — St. Louis) foi um pioneiro da computação, sendo o engenheiro principal no desenvolvimento do computador Harvard Mark I da IBM.

Novo!!: Máquina de Turing e Howard Aiken · Veja mais »

Inteligência artificial

Inteligência artificial (por vezes mencionada pela sigla em português IA ou pela sigla em inglês AI - artificial intelligence) é a inteligência similar à humana exibida por mecanismos ou software.

Novo!!: Máquina de Turing e Inteligência artificial · Veja mais »

Konrad Zuse

Konrad Zuse (Berlim, — Hünfeld) foi um engenheiro alemão e um pioneiro dos computadores.

Novo!!: Máquina de Turing e Konrad Zuse · Veja mais »

Kurt Gödel

Kurt Friedrich Gödel (Brünn, Áustria-Hungria, — Princeton, Estados Unidos) foi um filósofo, matemático e lógico austríaco, naturalizado norte-americano.

Novo!!: Máquina de Turing e Kurt Gödel · Veja mais »

Leonardo Torres y Quevedo

Leonardo Torres y Quevedo (le.oˈnarðo ˈtores i keˈβeðo; 28 de dezembro de 1852 – 18 de dezembro de 1936) foi um engenheiro civil e matemático espanhol.

Novo!!: Máquina de Turing e Leonardo Torres y Quevedo · Veja mais »

Martin Davis

Martin David Davis (Nova Iorque) é um matemático estadunidense.

Novo!!: Máquina de Turing e Martin Davis · Veja mais »

Marvin Minsky

Marvin Lee Minsky (Nova Iorque, -) foi um cientista cognitivo norte-americano.

Novo!!: Máquina de Turing e Marvin Minsky · Veja mais »

Maurice d'Ocagne

Philbert Maurice d'Ocagne (Paris, — Le Havre) foi um engenheiro e matemático francês.

Novo!!: Máquina de Turing e Maurice d'Ocagne · Veja mais »

Max Newman

Maxwell Herman Alexander Newman (Londres, 7 de fevereiro de 1897 — Cambridge, 22 de fevereiro de 1984) foi um matemático e criptólogo britânico.

Novo!!: Máquina de Turing e Max Newman · Veja mais »

Máquina abstrata

Uma máquina abstrata (ou computador abstrato) é um modelo teórico de um sistema computacional de hardware ou software usado para detalhar o funcionamento do sistema,Macura usado na teoria dos autômatos.

Novo!!: Máquina de Turing e Máquina abstrata · Veja mais »

Máquina de Post-Turing

A máquina de Post-Turing é uma "formulação de um programa" de um tipo especialmente simples de máquina de Turing, compreendendo uma variante do modelo de computação Turing-equivalente de Emil Post descrito abaixo.

Novo!!: Máquina de Turing e Máquina de Post-Turing · Veja mais »

Máquina de Turing não determinística

Máquina de Turing não-determinística em ciência da computação é uma máquina de Turing cujo mecanismo de controle atua como um autômato finito não-determinístico.

Novo!!: Máquina de Turing e Máquina de Turing não determinística · Veja mais »

Máquina de Turing universal

Em ciência da computação, uma máquina de Turing universal (MTU) é uma máquina de Turing que consegue simular outra máquina de Turing arbitrária com uma entrada arbitrária.

Novo!!: Máquina de Turing e Máquina de Turing universal · Veja mais »

Método efetivo

Em lógica e matemática - especialmente metalógica e teoria da computabilidade - método efetivo Hunter, Geoffrey, Metalogic: uma Introdução ao Metateoria de lógica de primeira ordem padrão, University of California Press, 1971 (também chamado de procedimento efetivo) é o procedimento para uma classe de problemas é um método para o qual cada passo pode ser descrito como uma operação mecânica, e que, se seguidas rigorosamente resulta em.

Novo!!: Máquina de Turing e Método efetivo · Veja mais »

Número de Gödel

Em lógica matemática, uma numeração de Gödel é uma função matemática que atribui a cada símbolo e fórmula bem formada de alguma linguagem formal um único número natural, chamado seu número de Gödel.

Novo!!: Máquina de Turing e Número de Gödel · Veja mais »

Paul Strathern

Paul Strathern (Londres, 1940) é um autor britânico de biografias, romances e livros de histórias e viagens.

Novo!!: Máquina de Turing e Paul Strathern · Veja mais »

Problemas de Hilbert

David Hilbert, o autor dos "23 problemas" Os Problemas de Hilbert são uma lista de 23 problemas em matemática propostos pelo matemático alemão David Hilbert na conferência do Congresso Internacional de Matemáticos de Paris em 1900.

Novo!!: Máquina de Turing e Problemas de Hilbert · Veja mais »

Robin Gandy

Robin Oliver Gandy (—) foi um matemático britânico.

Novo!!: Máquina de Turing e Robin Gandy · Veja mais »

Segunda Guerra Mundial

A Segunda Guerra Mundial foi um conflito militar global que durou de 1939 a 1945, envolvendo a maioria das nações do mundo — incluindo todas as grandes potências — organizadas em duas alianças militares opostas: os Aliados e o Eixo.

Novo!!: Máquina de Turing e Segunda Guerra Mundial · Veja mais »

Stephen Kleene

Stephen Cole Kleene (Hartford, — Madison) foi um matemático estadunidense.

Novo!!: Máquina de Turing e Stephen Kleene · Veja mais »

Teoria da computação

A teoria da computação é um subcampo da ciência da computação e matemática que busca determinar quais problemas podem ser computados em um dado modelo de computação.

Novo!!: Máquina de Turing e Teoria da computação · Veja mais »

Tese de Church-Turing

Na teoria da computabilidade, a Tese de Church-Turing ou Tese de Church, assim nomeada em referência a Alonzo Church e Alan Turing, é uma hipótese sobre a natureza de artefatos mecânicos de cálculo, como computadores, e sobre que tipo de algoritmos eles podem executar.

Novo!!: Máquina de Turing e Tese de Church-Turing · Veja mais »

Teste de Turing

2000 O Teste de Turing testa a capacidade de uma máquina exibir comportamento inteligente equivalente a um ser humano, ou indistinguível deste.

Novo!!: Máquina de Turing e Teste de Turing · Veja mais »

Universidade de Heidelberg

A Universidade de Heidelberg, ou, nas suas formas portugueas, de Heidelberga ou de Edelberga, oficialmente denominada Universidade de Heidelberg Ruprecht Karl (Ruprecht-Karls-Universität Heidelberg, em alemão) é uma universidade pública alemã, das mais prestigiadas universidades do país.

Novo!!: Máquina de Turing e Universidade de Heidelberg · Veja mais »

Vannevar Bush

Vannevar Bush (Chelsea, Massachusetts, — Belmont) foi um engenheiro, inventor e político estadunidense, conhecido pelo seu papel político no desenvolvimento da bomba atômica e pela ideia do memex — visto como um conceito pioneiro, precursor da world wide web.

Novo!!: Máquina de Turing e Vannevar Bush · Veja mais »

1912

---- (na numeração romana) foi um ano bissexto do século XX do actual Calendário Gregoriano, da Era de Cristo, e as suas letras dominicais foram G e F (52 semanas), teve início a uma segunda-feira e terminou a uma terça-feira.

Novo!!: Máquina de Turing e 1912 · Veja mais »

1936

---- (na numeração romana) foi um ano bissexto do século XX do actual Calendário Gregoriano, da Era de Cristo, e as suas letras dominicais foram E e D (53 semanas), teve início a uma quarta-feira e terminou a uma quinta-feira.

Novo!!: Máquina de Turing e 1936 · Veja mais »

1954

---- (na numeração romana) foi um ano comum do século XX do actual Calendário Gregoriano, da Era de Cristo, e a sua letra dominical foi C, teve 52 semanas, início a uma sexta-feira e terminou também a uma sexta-feira.

Novo!!: Máquina de Turing e 1954 · Veja mais »

1986

Sem descrição

Novo!!: Máquina de Turing e 1986 · Veja mais »

23 de junho

Sem descrição

Novo!!: Máquina de Turing e 23 de junho · Veja mais »

Redireciona aqui:

Função Turing-computável, Máquina de turing, Máquinas de Turing.

CessanteEntrada
Ei! Agora estamos em Facebook! »