Caracterizações de algoritmo - Algorithm characterizations

As caracterizações de algoritmo são tentativas de formalizar a palavra algoritmo . Algoritmo não tem uma definição formal geralmente aceita. Os pesquisadores estão trabalhando ativamente neste problema. Este artigo apresentará algumas das "caracterizações" da noção de "algoritmo" com mais detalhes.

O problema de definição

Nos últimos 200 anos, a definição de algoritmo tornou-se mais complicada e detalhada à medida que os pesquisadores tentavam definir o termo. Na verdade, pode haver mais de um tipo de "algoritmo". Mas a maioria concorda que o algoritmo tem algo a ver com a definição de processos generalizados para a criação de inteiros de "saída" de outros inteiros de "entrada" - "parâmetros de entrada" arbitrários e infinitos em extensão, ou limitados em extensão, mas ainda variáveis ​​- pela manipulação de símbolos distinguíveis (números de contagem) com coleções finitas de regras que uma pessoa pode executar com papel e lápis.

Os esquemas de manipulação de números mais comuns - tanto na matemática formal quanto na vida rotineira - são: (1) as funções recursivas calculadas por uma pessoa com papel e lápis, e (2) a máquina de Turing ou seus equivalentes de Turing - o registro primitivo modelo de máquina ou "contra-máquina", o modelo de máquina de acesso aleatório (RAM), o modelo de máquina de programa armazenado de acesso aleatório (RASP) e seu equivalente funcional "o computador ".

Quando estamos fazendo "aritmética", estamos, na verdade, calculando pelo uso de "funções recursivas" nos algoritmos taquigráficos que aprendemos na escola primária, por exemplo, somar e subtrair.

As provas de que cada "função recursiva" que podemos calcular manualmente podemos computar por máquina e vice-versa - observe o uso das palavras calcular versus calcular - é notável. Mas essa equivalência junto com a tese (afirmação não comprovada) de que isso inclui todos os cálculos / computação indica por que tanta ênfase foi colocada no uso de máquinas equivalentes de Turing na definição de algoritmos específicos, e por que a própria definição de "algoritmo" frequentemente se refere à " máquina de Turing ". Isso é discutido em mais detalhes na caracterização de Stephen Kleene .

A seguir estão resumos das caracterizações mais famosas (Kleene, Markov, Knuth) junto com aquelas que introduzem novos elementos - elementos que expandem ainda mais a definição ou contribuem para uma definição mais precisa.

[ Um problema matemático e seu resultado podem ser considerados como dois pontos em um espaço, e a solução consiste em uma sequência de etapas ou um caminho ligando-os. A qualidade da solução é função do caminho. Pode haver mais de um atributo definido para o caminho, por exemplo, comprimento, complexidade de forma, facilidade de generalização, dificuldade e assim por diante . ]

Hierarquia de Chomsky

Há mais consenso sobre a "caracterização" da noção de "algoritmo simples".

Todos os algoritmos precisam ser especificados em uma linguagem formal, e a "noção de simplicidade" surge da simplicidade da linguagem. A hierarquia de Chomsky (1956) é uma hierarquia de contenção de classes de gramáticas formais que geram linguagens formais . É usado para classificar linguagens de programação e máquinas abstratas .

Da perspectiva da hierarquia de Chomsky , se o algoritmo pode ser especificado em uma linguagem mais simples (do que irrestrita), ele pode ser caracterizado por esse tipo de linguagem, caso contrário, é um típico "algoritmo irrestrito".

Exemplos: uma linguagem de macro de "propósito geral", como M4, é irrestrita ( Turing completo ), mas a linguagem de macro do pré-processador C não, portanto, qualquer algoritmo expresso no pré - processador C é um "algoritmo simples".

Consulte também Relações entre classes de complexidade .

Características de um bom algoritmo

A seguir estão as características de um bom algoritmo;

  • Precisão: um bom algoritmo deve ter algumas etapas delineadas. As etapas devem ser exatas o suficiente e não variam.
  • Unicidade: cada passo dado no algoritmo deve dar um resultado definido, conforme declarado pelo autor do algoritmo. Os resultados não devem flutuar de forma alguma.
  • Viabilidade: o algoritmo deve ser possível e praticável na vida real. Não deve ser abstrato ou imaginário.
  • Entrada: um bom algoritmo deve ser capaz de aceitar um conjunto de entradas definidas.
  • Saída: um bom algoritmo deve ser capaz de produzir resultados como saída, de preferência soluções.
  • Finitude: o algoritmo deve parar após um certo número de instruções.
  • Generalidade: o algoritmo deve ser aplicado a um conjunto de entradas definidas.

1881 Reação negativa de John Venn à Máquina Lógica de W. Stanley Jevons de 1870

No início de 1870, W. Stanley Jevons apresentou uma "Máquina Lógica" (Jevons 1880: 200) para analisar um silogismo ou outra forma lógica, por exemplo, um argumento reduzido a uma equação booleana . Por meio do que Couturat (1914) chamou de "uma espécie de piano lógico [,] ... as igualdades que representam as premissas ... são" tocadas "em um teclado como o de uma máquina de escrever ... Quando todas as premissas foram "jogados", o painel mostra apenas aqueles constituintes cuja soma é igual a 1, isto é, ... seu todo lógico. Este método mecânico tem vantagem sobre o método geométrico de VENN ... "(Couturat 1914: 75).

Por sua vez, John Venn , um lógico contemporâneo de Jevons, não ficou nada entusiasmado, opinando que "não me parece que quaisquer artifícios atualmente conhecidos ou passíveis de serem descobertos realmente mereçam o nome de máquinas lógicas" (grifo do autor, Venn 1881: 120). Mas de uso histórico para a noção em desenvolvimento de "algoritmo" é sua explicação para sua reação negativa com respeito a uma máquina que "pode ​​servir a um propósito realmente valioso, permitindo-nos evitar o trabalho de outra forma inevitável":

(1) "Há, em primeiro lugar, a declaração de nossos dados em linguagem lógica precisa",
(2) "Em segundo lugar, temos que lançar essas declarações em uma forma adequada para a máquina trabalhar - neste caso, a redução de cada proposição às suas negações elementares",
(3) "Em terceiro lugar, há a combinação ou tratamento adicional de nossas instalações após essa redução,"
(4) "Finalmente, os resultados devem ser interpretados ou lidos. Este último geralmente dá origem a muita abertura para habilidade e sagacidade."

Ele conclui que "Não consigo ver que qualquer máquina possa esperar nos ajudar, exceto na terceira dessas etapas; de modo que parece muito duvidoso se alguma coisa desse tipo realmente merece o nome de um motor lógico." (Venn 1881: 119 –121).

1943, 1952 a caracterização de Stephen Kleene

Esta seção é mais longa e detalhada do que as outras por causa de sua importância para o tópico: Kleene foi a primeira a propor que todos os cálculos / cálculos - de todos os tipos, a totalidade de - podem ser equivalentemente (i) calculados pelo uso de cinco " operadores recursivos primitivos "mais um operador especial denominado operador mu , ou ser (ii) calculado pelas ações de uma máquina de Turing ou um modelo equivalente.

Além disso, ele opinou que qualquer um desses seria uma definição de algoritmo .

Um leitor que primeiro confrontar as palavras que se seguem pode ficar confuso, então uma breve explicação é necessária. Meios de cálculo feitos à mão, meios de computação feitos por máquina de Turing (ou equivalente). (Às vezes, um autor escorrega e troca as palavras). Uma "função" pode ser pensada como uma "caixa de entrada-saída" na qual uma pessoa coloca números naturais chamados "argumentos" ou "parâmetros" (mas apenas os números de contagem incluindo 0 - os inteiros não negativos) e obtém um único não negativo inteiro (convencionalmente chamado de "a resposta"). Pense na "caixa de funções" como um homenzinho calculando manualmente usando "recursão geral" ou computando por máquina de Turing (ou uma máquina equivalente).

"Efetivamente calculável / computável" é mais genérico e significa "calculável / computável por algum procedimento, método, técnica ... seja o que for ...". "Recursivo geral" era a maneira de Kleene escrever o que hoje é chamado apenas de "recursão"; entretanto, "recursão primitiva" - cálculo pelo uso dos cinco operadores recursivos - é uma forma menor de recursão que não tem acesso ao sexto operador mu adicional, necessário apenas em casos raros. Assim, a maior parte da vida continua exigindo apenas as "funções recursivas primitivas".

1943 "Thesis I", 1952 "Church's Thesis"

Em 1943, Kleene propôs o que veio a ser conhecido como a tese de Church :

" Tese I. Cada função efetivamente calculável (predicado efetivamente decidível) é recursiva geral" (afirmado pela primeira vez por Kleene em 1943 (reimpresso na página 274 em Davis, ed. The Undecidable ; aparece também literalmente em Kleene (1952) p.300)

Resumindo: para calcular qualquer função, as únicas operações de que uma pessoa precisa (tecnicamente, formalmente) são os 6 operadores primitivos de recursão "geral" (hoje em dia chamados de operadores das funções recursivas mu ).

A primeira declaração de Kleene sobre isso foi sob o título da seção " 12. Teorias algoritmicas ". Ele mais tarde amplificaria em seu texto (1952) da seguinte forma:

"Tese I e seu inverso fornecem a definição exata da noção de um procedimento de cálculo (decisão) ou algoritmo , para o caso de uma função (predicado) de números naturais" (p. 301, negrito adicionado para ênfase)

(Seu uso da palavra "decisão" e "predicado" estende a noção de calculabilidade para a manipulação mais geral de símbolos, como ocorre em "provas" matemáticas.)

Isso não é tão assustador quanto pode parecer - a recursão "geral" é apenas uma maneira de fazer nossas operações aritméticas cotidianas a partir dos cinco "operadores" das funções recursivas primitivas junto com o operador mu adicional , conforme necessário. Na verdade, Kleene dá 13 exemplos de funções recursivas primitivas e Boolos – Burgess – Jeffrey adiciona mais alguns, muitos dos quais serão familiares ao leitor - por exemplo, adição, subtração, multiplicação e divisão, exponenciação, a função CASE, concatenação, etc., etc .; para obter uma lista, consulte Algumas funções recursivas primitivas comuns .

Por que funções recursivas gerais em vez de funções recursivas primitivas?

Kleene et al. (cf §55 Funções recursivas gerais p. 270 em Kleene 1952) teve que adicionar um sexto operador de recursão chamado de operador de minimização (escrito como operador µ ou operador mu ) porque Ackermann (1925) produziu uma função de crescimento enorme - o Ackermann função - e Rózsa Péter (1935) produziu um método geral de criação de funções recursivas usando o argumento diagonal de Cantor , nenhum dos quais poderia ser descrito pelos 5 operadores de função recursiva primitiva. Com relação à função Ackermann:

"... em certo sentido, o comprimento do algoritmo de computação de uma função recursiva que também não é recursiva primitiva cresce mais rápido com os argumentos do que o valor de qualquer função recursiva primitiva" (Kleene (1935) reimpresso p. 246 em The Indecidível , mais nota de rodapé 13 no que diz respeito à necessidade de um operador adicional, negrito adicionado).

Mas a necessidade do operador mu é uma raridade. Conforme indicado acima pela lista de cálculos comuns de Kleene, uma pessoa continua sua vida computando alegremente funções recursivas primitivas sem medo de encontrar os números de monstros criados pela função de Ackermann (por exemplo , superexponenciação ).

1952 "Tese de Turing"

A Tese de Turing levanta a hipótese da computabilidade de "todas as funções computáveis" pelo modelo da máquina de Turing e seus equivalentes.

Para fazer isso de maneira eficaz, Kleene estendeu a noção de "computável" ampliando a rede - permitindo na noção de "funções" tanto "funções totais" quanto "funções parciais". Uma função total é aquela definida para todos os números naturais (inteiros positivos incluindo 0). Uma função parcial é definida para alguns números naturais, mas não todos - a especificação de "alguns" deve vir "na frente". Assim, a inclusão de "função parcial" estende a noção de função para funções "menos perfeitas". As funções totais e parciais podem ser calculadas manualmente ou por máquina.

Exemplos:
"Funções": inclui "subtração comum m  -  n " e "adição m  +  n "
"Função parcial": "Subtração comum" m  -  n é indefinida quando apenas números naturais (inteiros positivos e zero) são permitidos como entrada - por exemplo, 6 - 7 é indefinida
Função total: "Adição" m  +  n é definida para todos os inteiros positivos e zero.


Agora observamos a definição de Kleene de "computável" em um sentido formal:

Definição: "Uma função parcial φ é computável , se houver uma máquina M que a calcula" (Kleene (1952) p. 360)
"Definição 2.5. Uma função n -ary f ( x 1 , ..., x n ) é parcialmente computável se existe uma máquina de Turing Z tal que
f ( x 1 , ..., x n ) = Ψ Z ( n ) ( x 1 , ..., [ x n )
Nesse caso, dizemos que [máquina] Z calcula f . Se, além disso, f ( x 1 , ..., x n ) é uma função total, então ela é chamada computável "(Davis (1958) p. 10)

Assim, chegamos à Tese de Turing :

"Cada função que seria naturalmente considerada computável é computável ... por uma de suas máquinas ..." (Kleene (1952) p.376)

Embora Kleene não tenha dado exemplos de "funções computáveis" que outros deram. Por exemplo, Davis (1958) fornece tabelas de Turing para as funções Constante, Sucessora e Identidade, três dos cinco operadores das funções recursivas primitivas :

Computável por máquina de Turing:
Adição (também é a função Constante se um operando for 0)
Incremento (função sucessora)
Subtração comum (definida apenas se x y ). Portanto, " x  -  y " é um exemplo de uma função parcialmente computável.
Subtração adequada x y (conforme definido acima)
A função de identidade: para cada i , existe uma função U Z n = Ψ Z n ( x 1 , ..., x n ) que retira x i do conjunto de argumentos ( x 1 , ..., x n )
Multiplicação

Boolos – Burgess – Jeffrey (2002) fornecem as seguintes descrições em prosa de máquinas de Turing para:

Dobrando: 2 p
Paridade
Adição
Multiplicação

No que diz respeito à contra-máquina , um modelo abstrato de máquina equivalente à máquina de Turing:

Exemplos computáveis ​​pela máquina Abacus (cf Boolos – Burgess – Jeffrey (2002))
Adição
Multiplicação
Exposição: (uma descrição do fluxograma / diagrama de blocos do algoritmo)

Demonstrações de computabilidade por máquina de ábaco (Boolos – Burgess – Jeffrey (2002)) e por máquina de contador (Minsky 1967):

Os seis operadores de função recursiva:
  1. Função zero
  2. Função sucessora
  3. Função de identidade
  4. Função de composição
  5. Recursão primitiva (indução)
  6. Minimização

O fato de que os modelos ábaco / contra-máquina podem simular as funções recursivas fornece a prova de que: Se uma função é "computável por máquina", então ela é "calculável manualmente por recursão parcial". Teorema XXIX de Kleene:

" Teorema XXIX:" Toda função parcial computável φ é recursiva parcial ... "(itálico no original, p. 374).

O inverso aparece como seu Teorema XXVIII. Juntos, eles formam a prova de sua equivalência, o Teorema de Kleene XXX.

Tese de Church – Turing de 1952

Com seu Teorema XXX Kleene prova a equivalência das duas "Teses" - a Tese da Igreja e a Tese de Turing. (Kleene só pode hipotetizar (conjeturar) a verdade de ambas as teses - estas ele não provou ):

TEOREMA XXX: As seguintes classes de funções parciais ... têm os mesmos membros: (a) as funções recursivas parciais, (b) as funções computáveis ​​... " (p. 376)
Definição de "função parcial recursiva": "Uma função parcial φ é parcial recursiva em [as funções parciais] ψ 1 , ... ψ n se houver um sistema de equações E que define φ recursivamente a partir de [funções parciais] ψ 1 , ... ψ n "(p. 326)

Assim, pelo teorema de Kleene XXX: qualquer método de fazer números a partir de números de entrada - funções recursivas calculadas manualmente ou pela máquina de Turing ou equivalente - resulta em uma "função efetivamente calculável / computável ". Se aceitarmos a hipótese de que todo cálculo / computação pode ser feito por qualquer um dos métodos de maneira equivalente, aceitamos o Teorema XXX de Kleene (a equivalência) e a Tese de Church-Turing (a hipótese de "todos").

Uma nota de dissidência: "Há mais no algoritmo ..." Blass e Gurevich (2003)

A noção de separar as teses de Church e Turing da "tese de Church-Turing" aparece não apenas em Kleene (1952), mas também em Blass-Gurevich (2003). Mas, embora existam acordos, também existem divergências:

"... discordamos de Kleene de que a noção de algoritmo é bem compreendida. Na verdade, a noção de algoritmo é mais rica hoje em dia do que era na época de Turing. E há algoritmos, de variedades modernas e clássicas, não cobertos diretamente por A análise de Turing, por exemplo, algoritmos que interagem com seus ambientes, algoritmos cujas entradas são estruturas abstratas e algoritmos geométricos ou, mais geralmente, algoritmos não discretos "(Blass-Gurevich (2003) p. 8, negrito adicionado)

Caracterização de 1954 AA Markov Jr.

Andrey Markov Jr. (1954) forneceu a seguinte definição de algoritmo:

"1. Em matemática," algoritmo "é comumente entendido como uma prescrição exata, definindo um processo computacional, levando de vários dados iniciais ao resultado desejado ..."
"Os três recursos a seguir são característicos dos algoritmos e determinam seu papel na matemática:
“a) a precisão da prescrição, não deixando lugar à arbitrariedade, e sua compreensibilidade universal - a precisão do algoritmo;
“b) a possibilidade de partir dos dados iniciais, que podem variar dentro de determinados limites - a generalidade do algoritmo;
"c) a orientação do algoritmo para a obtenção de algum resultado desejado, que de fato é obtido no final com os dados iniciais adequados - a conclusividade do algoritmo." (p.1)

Ele admitiu que esta definição "não pretende precisão matemática" (p. 1). Sua monografia de 1954 foi sua tentativa de definir o algoritmo com mais precisão; ele viu sua definição resultante - seu algoritmo "normal" - como "equivalente ao conceito de uma função recursiva " (p. 3). Sua definição incluiu quatro componentes principais (Capítulo II.3 pp. 63ff):

"1. Etapas elementares separadas, cada uma das quais será realizada de acordo com uma das [regras de substituição] ... [regras fornecidas no início]
"2. ... passos de natureza local ... [Assim, o algoritmo não mudará mais do que um certo número de símbolos à esquerda ou à direita da palavra / símbolo observado]
"3. Regras para as fórmulas de substituição ... [chamou a lista dessas de" o esquema "do algoritmo]
"4. ... um meio para distinguir uma" substituição conclusiva "[ou seja, um estado ou estados" terminal / final "distinguíveis]

Em sua introdução, Markov observou que "todo o significado para a matemática" dos esforços para definir o algoritmo mais precisamente estaria "em conexão com o problema de uma base construtiva para a matemática" (p. 2). Ian Stewart (cf Encyclopædia Britannica) compartilha uma crença semelhante: "... a análise construtiva segue o mesmo espírito algorítmico da ciência da computação ...". Para mais informações, consulte matemática construtiva e intuicionismo .

Distinguibilidade e localidade : ambas as noções apareceram pela primeira vez com Turing (1936-1937) -

"Os novos quadrados observados devem ser imediatamente reconhecíveis pelo computador [ sic : um computador era uma pessoa em 1936]. Acho razoável supor que eles só podem ser quadrados cuja distância do mais próximo dos quadrados imediatamente observados não exceda um certa quantidade fixa. Vamos manter que cada um dos novos quadrados observados está dentro de L quadrados de um dos quadrados observados anteriormente. " (Turing (1936) p. 136 em Davis ed. Undecidable )

A localidade aparece com destaque na obra de Gurevich e Gandy (1980) (a quem Gurevich cita). O "Quarto Princípio para Mecanismos" de Gandy é "O Princípio da Causalidade Local":

"Agora chegamos ao mais importante dos nossos princípios. Na análise de Turing, o requisito de que a ação dependesse apenas de uma parte limitada do registro era baseada em uma limitação humana. Substituímos isso por uma limitação física que chamamos de princípio do local causação. Sua justificativa reside na velocidade finita de propagação de efeitos e sinais: a física contemporânea rejeita a possibilidade de ação instantânea à distância. " (Gandy (1980) p. 135 em J. Barwise et al.)

1936, 1963, 1964 caracterização de Gödel

1936 : Uma citação bastante famosa de Kurt Gödel aparece em uma "Observação adicionada à prova [da publicação original em alemão] em seu artigo" On the Length of Proofs "traduzido por Martin Davis aparecendo nas páginas 82-83 de The Undecidable . vários autores - Kleene, Gurevich, Gandy etc. - citaram o seguinte:

"Assim, o conceito de" computável "é, em certo sentido definido," absoluto ", enquanto praticamente todos os outros conceitos metamatemáticos familiares (por exemplo, demonstrável, definível etc.) dependem essencialmente do sistema com relação ao qual são definidos." (p. 83)

1963 : Em uma "Nota" datada de 28 de agosto de 1963 adicionada ao seu famoso artigo On Formally Undecidable Propositions (1931), Gödel afirma (em uma nota de rodapé) sua crença de que " sistemas formais " têm "a propriedade característica de que o raciocínio neles, em princípio, pode ser completamente substituído por dispositivos mecânicos "(p. 616 em van Heijenoort). "... devido ao" trabalho de AM Turing, uma definição precisa e inquestionavelmente adequada da noção geral de sistema formal pode agora ser dada [e] uma versão completamente geral dos Teoremas VI e XI agora é possível. "(p. 616). Em uma nota de 1964 para outra obra, ele expressa a mesma opinião de forma mais vigorosa e detalhada.

1964 : Em um PostScript, datado de 1964, para um artigo apresentado ao Institute for Advanced Study na primavera de 1934, Gödel ampliou sua convicção de que "sistemas formais" são aqueles que podem ser mecanizados:

"Em consequência de avanços posteriores, em particular do fato de que, devido ao trabalho de AM Turing, uma definição precisa e inquestionavelmente adequada do conceito geral de sistema formal pode agora ser dada... O trabalho de Turing fornece uma análise do conceito de" procedimento mecânico "(também conhecido como" algoritmo "ou" procedimento computacional "ou" procedimento combinatório finito "). Este conceito é mostrado como equivalente ao de uma" máquina de Turing ". * Um sistema formal pode simplesmente ser definido como qualquer procedimento mecânico para produzir fórmulas, chamadas fórmulas prováveis.... " (p. 72 em Martin Davis ed. The Undecidable : "Postscriptum" to "On Undecidable Propositions of Formal Mathematical Systems" aparecendo na p. 39, loc. cit.)

O * indica uma nota de rodapé em que Gödel cita os artigos de Alan Turing (1937) e Emil Post (1936) e, em seguida, faz a seguinte declaração intrigante:

"Quanto às definições equivalentes anteriores de computabilidade, que, no entanto, são muito menos adequadas para o nosso propósito, ver Alonzo Church , Am. J. Math., Vol. 58 (1936) [publicado em The Undecidable pp. 100-102]).

As definições de Church englobam a chamada " recursão " e o " cálculo lambda " (ou seja, as funções definíveis por λ). Sua nota de rodapé 18 diz que ele discutiu a relação de "calculabilidade efetiva" e "recursividade" com Gödel, mas que ele questionou independentemente "calculabilidade efetiva" e "definibilidade λ":

"Agora definimos a noção ... de uma função efetivamente calculável de inteiros positivos, identificando-a com a noção de uma função recursiva de inteiros positivos 18 (ou de uma função definível por λ de inteiros positivos.
“Já foi apontado que, para cada função de inteiros positivos efetivamente calculáveis ​​no sentido que acabamos de definir, existe um algoritmo de cálculo do seu valor.
"Inversamente, é verdade..." (p. 100, O indecidível).

A partir disso, e do seguinte, pareceria que, no que dizia respeito a Gödel, a máquina de Turing era suficiente e o cálculo lambda era "muito menos adequado". Ele prossegue afirmando que, no que diz respeito às limitações da razão humana, o júri ainda está aberto:

("Observe que a questão de saber se existem procedimentos não mecânicos finitos ** não equivalentes a nenhum algoritmo, não tem nada a ver com a adequação da definição de" sistema formal "e de" procedimento mecânico ".) (P. 72, loc. Cit.)
"(Para teorias e procedimentos no sentido mais geral indicado na nota de rodapé **, a situação pode ser diferente. Observe que os resultados mencionados no pós-escrito não estabelecem quaisquer limites para os poderes da razão humana, mas sim para as potencialidades do puro formalismo em matemática.) (p. 73 loc. cit.)
Nota de rodapé **: "Ie, como envolve o uso de termos abstratos com base em seu significado. Veja meu artigo em Dial. 12 (1958), p. 280." (esta nota de rodapé aparece na p. 72, loc. cit).

Caracterização de Minsky de 1967

Minsky (1967) afirma categoricamente que "um algoritmo é" um procedimento eficaz "e se recusa a usar a palavra" algoritmo "mais adiante em seu texto; na verdade, seu índice deixa claro o que ele sente sobre" Algoritmo, sinônimo de procedimento eficaz "( p. 311):

"Usaremos o último termo [um procedimento eficaz ] na sequência. Os termos são aproximadamente sinônimos, mas há uma série de nuances de significado usadas em diferentes contextos, especialmente para 'algoritmo'" (itálico no original, p. 105 )

Outros escritores (veja Knuth abaixo) usam a palavra "procedimento eficaz". Isso nos leva a perguntar: Qual é a noção de Minsky de "um procedimento eficaz"? Ele começa com:

"... um conjunto de regras que nos dizem, de momento a momento, precisamente como nos comportar" (p. 106)

Mas ele reconhece que isso está sujeito a uma crítica:

"... a crítica de que a interpretação das regras fica por conta de alguma pessoa ou agente" (p. 106)

Seu refinamento? "Especificar, junto com o enunciado das regras, os detalhes do mecanismo que as deve interpretar ". Para evitar o processo "complicado" de "ter que fazer isso novamente para cada procedimento individual", ele espera identificar uma " família razoavelmente uniforme de mecanismos de obediência às regras". Sua "formulação":

"(1) uma linguagem em que conjuntos de regras de comportamento devem ser expressos, e
"(2) uma única máquina que pode interpretar declarações na linguagem e, assim, realizar as etapas de cada processo especificado." (itálico no original, todas as citações deste parágrafo. p. 107)

No final, porém, ele ainda se preocupa que "ainda resta um aspecto subjetivo do assunto. Diferentes pessoas podem não concordar sobre se um determinado procedimento deve ser considerado eficaz" (p. 107)

Mas Minsky não se intimidou. Ele imediatamente introduz "Análise do processo de computação de Turing" (seu capítulo 5.2). Ele cita o que chama de " tese de Turing "

"Qualquer processo que poderia naturalmente ser chamado de procedimento eficaz pode ser realizado por uma máquina de Turing" (p. 108. (Minsky comenta que, de uma forma mais geral, isso é chamado de " tese de Church ").

Após uma análise do "Argumento de Turing" (seu capítulo 5.3), ele observa que a "equivalência de muitas formulações intuitivas" de Turing, Church, Kleene, Post e Smullyan "... nos leva a supor que realmente há aqui um objetivo 'ou noção' absoluta '. Como disse Rogers [1959]:

"Nesse sentido, a noção de função efetivamente computável é um dos poucos conceitos 'absolutos' produzidos pelo trabalho moderno nos fundamentos da matemática '" (Minsky p. 111 citando Rogers, Hartley Jr (1959) A presente teoria da máquina de Turing computabilidade , J. SIAM 7, 114-130.)

Caracterização de Rogers de 1967

Em sua Teoria de Funções Recursivas e Computabilidade Efetiva de 1967, Hartley Rogers caracteriza "algoritmo" aproximadamente como "um procedimento clerical (isto é, determinístico, contábil) ... aplicado a ... entradas simbólicas e que eventualmente renderá, para cada uma dessas entradas , uma saída simbólica correspondente "(p. 1). Ele então passa a descrever a noção "em termos aproximados e intuitivos" como tendo 10 "características", 5 das quais ele afirma que "virtualmente todos os matemáticos concordariam [com]" (p. 2). Os 5 restantes, ele afirma "são menos óbvios do que * 1 a * 5 e sobre os quais podemos encontrar menos concordância geral" (p. 3).

Os 5 "óbvios" são:

  • 1 Um algoritmo é um conjunto de instruções de tamanho finito,
  • 2 Existe um agente de computação capaz,
  • 3 "Existem recursos para fazer, armazenar e recuperar etapas em um cálculo"
  • 4 Dados # 1 e # 2, o agente calcula de "forma discreta em etapas" sem o uso de métodos contínuos ou dispositivos analógicos ",
  • 5 O agente de computação leva a computação adiante "sem recorrer a métodos ou dispositivos aleatórios, por exemplo, dados" (em uma nota de rodapé, Rogers se pergunta se os números 4 e 5 são realmente iguais)

Os 5 restantes que ele abre para debate são:

  • 6 Sem limite fixo no tamanho das entradas,
  • 7 Não há limite fixo no tamanho do conjunto de instruções,
  • 8 Nenhum limite fixo na quantidade de armazenamento de memória disponível,
  • 9 Um limite finito fixo na capacidade ou habilidade do agente de computação (Rogers ilustra com exemplos de mecanismos simples semelhantes a uma máquina de Post-Turing ou contra-máquina ),
  • 10 Um limite no comprimento do cálculo - "devemos ter alguma idéia, 'antecipadamente', quanto tempo o cálculo levará?" (p. 5). Rogers exige "apenas que um cálculo termine após algum número finito de etapas; não insistimos em uma capacidade a priori de estimar esse número." (p. 5).

1968, 1973 a caracterização de Knuth

Knuth (1968, 1973) forneceu uma lista de cinco propriedades que são amplamente aceitas como requisitos para um algoritmo:

  1. Finitude : "Um algoritmo deve sempre terminar após um número finito de etapas ... um número muito finito, um número razoável"
  2. Definição : "Cada etapa de um algoritmo deve ser definida com precisão; as ações a serem realizadas devem ser rigorosamente e inequivocamente especificadas para cada caso"
  3. Entrada : "... quantidades que são fornecidas a ele inicialmente antes do início do algoritmo. Essas entradas são obtidas de conjuntos de objetos especificados"
  4. Saída : "... quantidades que têm uma relação específica com as entradas"
  5. Eficácia : "... todas as operações a serem realizadas no algoritmo devem ser suficientemente básicas para que possam, em princípio, ser feitas exatamente e em um período de tempo finito por um homem usando papel e lápis"

Knuth oferece como exemplo o algoritmo euclidiano para determinar o maior divisor comum de dois números naturais (cf. Knuth, Vol. 1, p. 2).

Knuth admite que, embora sua descrição de um algoritmo possa ser intuitivamente clara, ela carece de rigor formal, uma vez que não é exatamente claro o que significa "precisamente definido", ou "rigorosa e inequivocamente especificado" significa, ou "suficientemente básico", e assim para frente. Ele se esforça nesse sentido em seu primeiro volume, onde define em detalhes o que chama de " linguagem de máquina " para seu "mítico MIX ... o primeiro computador poliinsaturado do mundo" (pp. 120ss). Muitos dos algoritmos em seus livros são escritos na linguagem MIX. Ele também usa diagramas de árvore , diagramas de fluxo e diagramas de estado .

"Bondade" de um algoritmo, "melhores" algoritmos : Knuth afirma que "Na prática, não queremos apenas algoritmos, queremos bons algoritmos ...." Ele sugere que alguns critérios da bondade de um algoritmo são o número de etapas a serem executadas o algoritmo, sua "adaptabilidade aos computadores, sua simplicidade e elegância, etc." Dado um número de algoritmos para realizar o mesmo cálculo, qual é o "melhor"? Ele chama esse tipo de investigação de "análise algorítmica: dado um algoritmo, para determinar suas características de desempenho" (todas as citações deste parágrafo: Knuth Vol. 1 p. 7)

Caracterização de Stone de 1972

Stone (1972) e Knuth (1968, 1973) eram professores na Universidade de Stanford ao mesmo tempo, então não é surpreendente se houver semelhanças em suas definições (negrito adicionado para ênfase):

"Para resumir ... nós definimos um algoritmo como um conjunto de regras que define precisamente uma sequência de operações de forma que cada regra seja efetiva e definida e que a sequência termine em um tempo finito." (negrito adicionado, p. 8)

Stone é digno de nota por causa de sua discussão detalhada sobre o que constitui uma regra "eficaz" - seu robô , ou pessoa agindo como robô, deve ter algumas informações e habilidades dentro deles, e se não, a informação e a habilidade devem ser fornecidas em "o algoritmo":

“Para que as pessoas sigam as regras de um algoritmo, as regras devem ser formuladas de forma que possam ser seguidas de forma robótica , ou seja, sem a necessidade de pensar ... porém, se as instruções [para resolver o quadrático equação, seu exemplo] devem ser obedecidos por alguém que sabe como realizar operações aritméticas, mas não sabe como extrair uma raiz quadrada, então devemos também fornecer um conjunto de regras para extrair uma raiz quadrada a fim de satisfazer a definição de algoritmo "(p. 4-5)

Além disso, "... nem todas as instruções são aceitáveis , porque podem exigir que o robô tenha habilidades além daquelas que consideramos razoáveis ." Ele dá o exemplo de um robô confrontado com a pergunta "Henry VIII um rei da Inglaterra?" e imprimir 1 se sim e 0 se não, mas o robô não recebeu essa informação anteriormente. E pior, se o robô for perguntado se Aristóteles era um rei da Inglaterra e o robô só recebeu cinco nomes, não saberia responder. Assim:

“Uma definição intuitiva de uma sequência aceitável de instruções é aquela em que cada instrução é definida com precisão para que o robô tenha a garantia de ser capaz de obedecê-la ” (p. 6)

Depois de nos fornecer sua definição, Stone apresenta o modelo da máquina de Turing e afirma que o conjunto de cinco tuplas que são as instruções da máquina são “um algoritmo ... conhecido como programa da máquina de Turing” (p. 9). Imediatamente depois disso, ele continua a dizer que um " cálculo de uma máquina de Turing é descrito afirmando:

"1. O alfabeto da fita
"2. A forma em que os parâmetros de [entrada] são apresentados na fita
"3. O estado inicial da máquina de Turing
"4. A forma em que as respostas [saída] será representada na fita quando a máquina de Turing parar
"5. O programa da máquina" (itálico adicionado, p. 10)

Esta prescrição precisa do que é necessário para "um cálculo" está no espírito do que se seguirá na obra de Blass e Gurevich.

Caracterização de Soare em 1995

"Um cálculo é um processo pelo qual procedemos de objetos inicialmente dados, chamados de entradas , de acordo com um conjunto fixo de regras, chamado de programa, procedimento ou algoritmo , por meio de uma série de etapas e chegamos ao final dessas etapas com um final resultado, chamado de saída . O algoritmo , como um conjunto de regras que vão de entradas para saídas, deve ser preciso e definido com cada etapa sucessiva claramente determinada. O conceito de computabilidade diz respeito aos objetos que podem ser especificados em princípio por cálculos. "(itálico no original, negrito adicionado p. 3)

Caracterização de Berlinski de 2000

Enquanto estudante em Princeton em meados da década de 1960, David Berlinski era aluno da Igreja Alonzo (cf p. 160). Seu livro do ano 2000, O Advento do Algoritmo: A Viagem de 300 anos de uma Idéia ao Computador, contém a seguinte definição de algoritmo :

" Na voz do lógico:
" um algoritmo é
um procedimento finito,
escrito em um vocabulário simbólico fixo,
regido por instruções precisas,
movendo-se em etapas discretas, 1, 2, 3,. . .,
cuja execução não requer discernimento, inteligência,
intuição, inteligência ou perspicuidade,
e isso mais cedo ou mais tarde chega ao fim. "(negrito e itálico no original, p. xviii)

2000, 2002 caracterização de Gurevich

Uma leitura cuidadosa de Gurevich 2000 leva alguém a concluir (inferir?) Que ele acredita que "um algoritmo" é na verdade "uma máquina de Turing" ou "uma máquina de ponteiro " fazendo um cálculo. Um "algoritmo" não é apenas a tabela de símbolos que orienta o comportamento da máquina, nem é apenas uma instância de uma máquina fazendo um cálculo dado um determinado conjunto de parâmetros de entrada, nem é uma máquina adequadamente programada com a energia desligada ; em vez disso, um algoritmo é a máquina que realmente faz qualquer cálculo de que seja capaz . Gurevich não vem direto ao ponto e diz isso, então, como formulado acima, esta conclusão (inferência?) Certamente está aberta ao debate:

"... todo algoritmo pode ser simulado por uma máquina de Turing ... um programa pode ser simulado e, portanto, recebe um significado preciso por uma máquina de Turing." (p. 1)
“Costuma-se pensar que o problema de formalizar a noção de algoritmo sequencial foi resolvido por Church [1936] e Turing [1936]. Por exemplo, de acordo com Savage [1987], um algoritmo é um processo computacional definido por uma máquina de Turing. Church e Turing não resolveram o problema de formalizar a noção de algoritmo sequencial. Em vez disso, deram formalizações (diferentes, mas equivalentes) da noção de função computável, e um algoritmo é mais do que a função que ele calcula (itálico adicionado p. 3)
"Claro, as noções de algoritmo e função computável estão intimamente relacionadas: por definição, uma função computável é uma função computável por um algoritmo ... (p. 4)


Em Blass e Gurevich 2002, os autores invocam um diálogo entre "Quisani" ("Q") e "Authors" (A), usando Yiannis Moshovakis como uma folha, de onde eles vêm direto e afirmam categoricamente:

" R: Para localizar a discordância, vamos primeiro mencionar dois pontos de concordância. Primeiro, há algumas coisas que são obviamente algoritmos por definição - máquinas de Turing, ASMs de tempo sequencial [Máquinas de estado abstrato] e semelhantes. . Em segundo lugar, no outro extremo estão as especificações que não seriam consideradas algoritmos pela definição de ninguém, uma vez que não fornecem nenhuma indicação de como computar nada... A questão é quão detalhada a informação deve ser para contar como um algoritmo. (...) Moshovakis permite algumas coisas que chamaríamos apenas de especificações declarativas e provavelmente usaria a palavra "implementação" para coisas que chamamos de algoritmos ". (parágrafos unidos para facilitar a leitura, 2002: 22)

Esse uso da palavra "implementação" vai direto ao cerne da questão. No início do artigo, Q declara sua leitura de Moshovakis:

"... [Ele] provavelmente pensaria que seu trabalho prático [Gurevich trabalha para a Microsoft] força você a pensar mais em implementações do que em algoritmos. Ele está bastante disposto a identificar implementações com máquinas, mas diz que algoritmos são algo mais geral. O que se resume a isso é que você diz que um algoritmo é uma máquina e Moschovakis diz que não. " (2002: 3)

Mas os autores gaguejam aqui, dizendo "[Vamos ficar com" algoritmo "e" máquina ", e o leitor fica, novamente, confuso. Temos que esperar até Dershowitz e Gurevich 2007 para obter o seguinte comentário de nota de rodapé:

"... No entanto, se aceitarmos o ponto de vista de Moshovakis, então é a" implementação "de algoritmos que nos propusemos a caracterizar." (Cf Nota de rodapé 9 2007: 6)

Caracterização de Blass e Gurevich de 2003

Blass e Gurevich descrevem seu trabalho como evoluído a partir da consideração de máquinas de Turing e máquinas apontadoras , especificamente máquinas Kolmogorov-Uspensky (máquinas KU), Máquinas de modificação de armazenamento Schönhage (SMM) e autômatos de ligação conforme definido por Knuth. Os trabalhos de Gandy e Markov também são descritos como precursores influentes.

Gurevich oferece uma definição 'forte' de um algoritmo (negrito adicionado):

"... O argumento informal de Turing em favor de sua tese justifica uma tese mais forte: todo algoritmo pode ser simulado por uma máquina de Turing ... Na prática, seria ridículo ... [No entanto,] [c] generalizar Máquinas de Turing para que qualquer algoritmo, por mais abstrato que seja, possa ser modelado por uma máquina generalizada? ... Mas suponha que tais máquinas de Turing generalizadas existam. Quais seriam seus estados? ... uma estrutura de primeira ordem ... uma estrutura particular pequeno conjunto de instruções é suficiente em todos os casos ... computação como uma evolução do estado ... pode ser não determinística ... pode interagir com seu ambiente ... [poderia ser] paralelo e multiagente ... [poderia ter] semântica dinâmica ... [os dois fundamentos de seu trabalho são:] a tese de Turing ... [e] a noção de estrutura (de primeira ordem) de [Tarski 1933] "(Gurevich 2000, p. 1-2)

A frase acima, computação como uma evolução do estado, difere notavelmente da definição de Knuth e Stone - o "algoritmo" como um programa de máquina de Turing. Pelo contrário, ela corresponde ao que Turing chamou a configuração completa (cf. definição de Turing em Indecidíveis, p 118.) - e inclui tanto a instrução atual (estado) e o estado da fita. [cf Kleene (1952) p. 375 onde ele mostra um exemplo de uma fita com 6 símbolos nela - todos os outros quadrados estão em branco - e como Gödelize seu status combinado de fita de mesa].

Nos exemplos de algoritmos , vemos a evolução do estado em primeira mão.

1995 - Daniel Dennett: a evolução como um processo algorítmico

O filósofo Daniel Dennett analisa a importância da evolução como um processo algorítmico em seu livro de 1995, Darwin's Dangerous Idea . Dennett identifica três características principais de um algoritmo:

  • Neutralidade do substrato : um algoritmo depende de sua estrutura lógica . Assim, a forma particular na qual um algoritmo se manifesta não é importante (o exemplo de Dennett é a divisão longa: funciona igualmente bem no papel, no pergaminho, na tela do computador, ou usando luzes de néon ou escrita no céu). (p. 51)
  • Estupidez subjacente : não importa quão complicado seja o produto final do processo algorítmico, cada etapa do algoritmo é suficientemente simples para ser executada por um dispositivo mecânico não senciente. O algoritmo não requer um "cérebro" para mantê-lo ou operá-lo. “A analogia do livro texto padrão observa que algoritmos são receitas de uma espécie, projetadas para serem seguidas por cozinheiros novatos .” (P. 51)
  • Resultados garantidos : Se o algoritmo for executado corretamente, sempre produzirá os mesmos resultados. "Um algoritmo é uma receita infalível." (p. 51)

É com base nessa análise que Dennett conclui que "De acordo com Darwin, a evolução é um processo algorítmico". (p. 60).

No entanto, na página anterior, ele avançou muito mais. No contexto de seu capítulo intitulado "Processos as Algorithms", ele afirma:

"Mas então ... há algum limite sobre o que pode ser considerado um processo algorítmico? Acho que a resposta é NÃO; se você quiser, pode tratar qualquer processo no nível abstrato como um processo algorítmico ... Se o quê parece intrigante para você é a uniformidade dos grãos de areia [do oceano] ou a força da lâmina [de aço temperado], uma explicação algorítmica é o que irá satisfazer sua curiosidade - e será a verdade.
"Não importa o quão impressionante os produtos de um algoritmo, o processo subjacente sempre consiste em nada além de um conjunto de individualy [ sic ] passos estúpidos sucedem uns aos outros sem a ajuda de qualquer supervisão inteligente, pois eles são 'automática' por definição: o funcionamento do um autômato. " (p. 59)

Não está claro pelo que foi dito acima se Dennett está afirmando que o mundo físico por si só e sem observadores é intrinsecamente algorítmico (computacional) ou se um observador de processamento de símbolos é o que está adicionando "significado" às observações.

2002 John Searle adiciona uma advertência esclarecedora à caracterização de Dennett

Daniel Dennett é um defensor da inteligência artificial forte : a ideia de que a estrutura lógica de um algoritmo é suficiente para explicar a mente . John Searle , o criador do experimento mental do quarto chinês , afirma que "a sintaxe [isto é, a estrutura lógica] por si só não é suficiente para o conteúdo semântico [isto é, o significado]" ( Searle 2002 , p. 16). Em outras palavras, o "significado" dos símbolos é relativo à mente que os está usando; um algoritmo - uma construção lógica - por si só é insuficiente para uma mente.

Searle alerta aqueles que afirmam que os processos algorítmicos (computacionais) são intrínsecos à natureza (por exemplo, cosmologistas, físicos, químicos, etc.):

A computação é relativa ao observador, e isso ocorre porque a computação é definida em termos de manipulação de símbolos, mas a noção de um 'símbolo' não é uma noção de física ou química. Algo é um símbolo apenas se for usado, tratado ou considerado como um símbolo. O argumento da sala chinesa mostrou que a semântica não é intrínseca à sintaxe. Mas o que isso mostra é que a sintaxe não é intrínseca à física. [...] Algo é um símbolo apenas relativo a algum observador, usuário ou agente que atribui uma interpretação simbólica a ele [...] você pode atribuir uma interpretação computacional a qualquer coisa. Mas se a pergunta for: "A consciência é intrinsecamente computacional?" a resposta é: nada é intrinsecamente computacional [itálico adicionado para dar ênfase]. A computação existe apenas em relação a algum agente ou observador que impõe uma interpretação computacional a algum fenômeno. Este é um ponto óbvio. Eu deveria ter visto isso há dez anos, mas não vi.

-  John Searle, Searle 2002 , p. 17

2002: Especificação Boolos-Burgess-Jeffrey do cálculo da máquina de Turing

Para exemplos deste método de especificação aplicado ao algoritmo de adição "m + n", consulte Exemplos de algoritmos .

Um exemplo em Boolos-Burgess-Jeffrey (2002) (pp. 31–32) demonstra a precisão necessária em uma especificação completa de um algoritmo, neste caso para adicionar dois números: m + n. É semelhante aos requisitos de Pedra acima.

(i) Eles discutiram o papel do "formato de número" no cálculo e selecionaram a "notação de contagem" para representar os números:

"Certamente, a computação pode ser mais difícil na prática com algumas notações do que outras ... Mas ... é possível, em princípio, fazer em qualquer outra notação, simplesmente traduzindo os dados ... Para fins de enquadramento de uma noção rigorosamente definida de computabilidade , é conveniente usar a notação monádica ou de contagem "(p. 25-26)

(ii) No início de seu exemplo, eles especificam a máquina a ser usada no cálculo como uma máquina de Turing . Eles especificaram anteriormente (p. 26) que a máquina de Turing será da variedade de 4 tuplas, em vez de 5 tuplas. Para mais informações sobre esta convenção, consulte Máquina de Turing .

(iii) Anteriormente, os autores especificaram que a posição da cabeça da fita será indicada por um subscrito à direita do símbolo digitalizado. Para mais informações sobre esta convenção, consulte Máquina de Turing . (A seguir, negrito é adicionado para dar ênfase):

"Não demos uma definição oficial do que significa uma função numérica ser computável por uma máquina de Turing , especificando como as entradas ou argumentos devem ser representados na máquina e como as saídas ou valores são representados. Nossas especificações para um k- função de lugar de inteiros positivos para inteiros positivos são os seguintes:
"(a) [ Formato de número inicial: ] Os argumentos m 1 , ... m k , ... serão representados em notação monádica [unária] por blocos desses números de traços, cada bloco separado do próximo por um único em branco, em uma fita em branco.
Exemplo: 3 + 2, 111B11
"(b) [ Localização inicial da cabeça, estado inicial: ] Inicialmente, a máquina fará a varredura do 1 mais à esquerda na fita e estará em seu estado inicial, estado 1.
Exemplo: 3 + 2, 1 1 111B11
"(c) [ Cálculo bem-sucedido - formato de número na parada: ] Se a função a ser computada atribuir um valor n aos argumentos que são representados inicialmente na fita, então a máquina irá eventualmente parar em uma fita contendo um bloco de traços , e em branco ...
Exemplo: 3 + 2, 11111
"(d) [ Cálculo bem-sucedido - localização da cabeça na parada: ] Neste caso [c] a máquina irá parar de escanear o 1 mais à esquerda na fita ...
Exemplo: 3 + 2, 1 n 1111
"(e) [ Cálculo malsucedido - falha em parar ou parar com formato de número não padrão: ] Se a função a ser calculada não atribui valor aos argumentos que são representados inicialmente na fita, então a máquina também nunca irá interromperá ou irá parar em alguma configuração fora do padrão ... "(ibid)
Exemplo: B n 11111 ou B11 n 111 ou B11111 n

Esta especificação está incompleta: requer a localização de onde as instruções devem ser colocadas e seu formato na máquina -

(iv) na TABELA da máquina de estado finito ou, no caso de uma máquina de Turing Universal na fita, e
(v) a Tabela de instruções em um formato especificado

Este último ponto é importante. Boolos-Burgess-Jeffrey dá uma demonstração (p. 36) de que a previsibilidade das entradas na tabela permite "encolher" a tabela colocando as entradas em sequência e omitindo o estado da entrada e o símbolo. Na verdade, o exemplo de computação da máquina de Turing exigiu apenas as 4 colunas, conforme mostrado na tabela abaixo (mas observe: elas foram apresentadas à máquina em linhas ):

Estado qk
Símbolo escaneado
Açao
Próximo estado qk
Estado qn
Símbolo escaneado
Açao
Próximo estado qk
Estado qk
Ação B
B-próximo estado qkB
1 ação
1: próximo estado qk1
1 B R H 1 1 R 2 1 R H R 2
2 B P 3 2 1 R 2 2 P 3 R 2
3 B eu 4 3 1 R 3 3 eu 4 R 3
4 B eu 5 4 1 E 4 4 eu 5 E 4
5 B R H 5 1 eu 5 5 R H eu 5

2006: Afirmação de Sipser e seus três níveis de descrição

Para exemplos deste método de especificação aplicado ao algoritmo de adição "m + n", consulte Exemplos de algoritmos .

Sipser começa definindo '"algoritmo" como segue:

"Falando informalmente, um algoritmo é uma coleção de instruções simples para realizar alguma tarefa. Comum na vida cotidiana, os algoritmos às vezes são chamados de procedimentos ou receitas (itálico no original, p. 154)
"... nosso foco real de agora em diante são os algoritmos. Ou seja, a máquina de Turing serve apenas como um modelo preciso para a definição do algoritmo ... precisamos apenas estar confortáveis ​​o suficiente com as máquinas de Turing para acreditar que elas capturam todos os algoritmos "(p. 156)

Sipser quer dizer que "algoritmo" é apenas "instruções" para uma máquina de Turing ou é a combinação de "instruções + uma (variedade específica de) máquina de Turing"? Por exemplo, ele define as duas variantes padrão (multi-tape e não determinística) de sua variante particular (diferente da original de Turing) e segue, em seus Problemas (páginas 160-161), para descrever mais quatro variantes ( escrever uma vez, fita duplamente infinita (ou seja, infinito à esquerda e à direita), redefinir à esquerda e "ficar parado em vez de à esquerda). Além disso, ele impõe algumas restrições. Primeiro, a entrada deve ser codificada como uma string (p. 157) e afirma de codificações numéricas no contexto da teoria da complexidade:

"Mas observe que a notação unária para números de codificação (como no número 17 codificado pelo número unário 11111111111111111) não é razoável porque é exponencialmente maior do que as codificações verdadeiramente razoáveis, como a notação de base k para qualquer k ≥ 2." (p. 259)

Van Emde Boas comenta um problema semelhante com relação ao modelo abstrato de computação da máquina de acesso aleatório (RAM) às vezes usado no lugar da máquina de Turing ao fazer "análise de algoritmos": "A ausência ou presença de manipulação de bits multiplicativos e paralelos operações é de relevância para o correto entendimento de alguns resultados na análise de algoritmos.

"... [T] aqui dificilmente existe algo como uma extensão" inocente "do modelo RAM padrão nas medidas de tempo uniformes; ou um só tem aritmética aditiva ou pode-se também incluir todos os multiplicativos razoáveis ​​e / ou bit a bit Instruções booleanas sobre pequenos operandos. " (Van Emde Boas, 1990: 26)

No que diz respeito a uma "linguagem de descrição" para algoritmos, Sipser termina o trabalho que Stone e Boolos-Burgess-Jeffrey começaram (negrito adicionado). Ele nos oferece três níveis de descrição dos algoritmos da máquina de Turing (p. 157):

Descrição de alto nível : "em que usamos ... prosa para descrever um algoritmo, ignorando os detalhes de implementação. Nesse nível, não precisamos mencionar como a máquina gerencia sua fita ou cabeça."
Descrição da implementação : "em que usamos ... prosa para descrever a maneira como a máquina de Turing move sua cabeça e a maneira como ela armazena dados em sua fita. Nesse nível, não fornecemos detalhes de estados ou função de transição."
Descrição formal : "... o nível de descrição mais baixo e mais detalhado ... que especifica por completo os estados da máquina de Turing, a função de transição e assim por diante."

Notas

Referências

  • David Berlinski (2000), The Advent of the Algorithm: The 300-Year Journey from an Idea to the Computer , Harcourt, Inc., San Diego, ISBN   0-15-601391-6 (pbk.)
  • George Boolos , John P. Burgess , Richard Jeffrey (2002), Computabilidade e Lógica: Quarta Edição , Cambridge University Press, Cambridge, Reino Unido. ISBN   0-521-00758-5 (pbk).
  • Andreas Blass e Yuri Gurevich (2003), Algorithms: A Quest for Absolute Definitions , Boletim da European Association for Theoretical Computer Science 81, 2003. Inclui uma excelente bibliografia de 56 referências.
  • Burgin, M. Algoritmos super-recursivos , Monografias em ciência da computação, Springer, 2005. ISBN   0-387-95569-0
  • Davis, Martin (1958). Computabilidade e insolubilidade . Nova York: McGraw-Hill Book Company, Inc. . Uma fonte de definições importantes e alguns algoritmos baseados em máquina de Turing para algumas funções recursivas.
  • Davis, Martin (1965). The Undecidable: Basic Papers on Undecidable Propositions, Unsolvable Problems and Computable Functions . Nova York: Raven Press. Davis faz comentários antes de cada artigo. Artigos de Gödel , Alonzo Church , Turing , Rosser , Kleene e Emil Post estão incluídos.
  • Dennett, Daniel (1995). A ideia perigosa de Darwin . Nova York: Touchstone / Simon & Schuster.
  • Robin Gandy , Church's Thesis and sources for Mechanisms , em J. Barwise , HJ Keisler e K. Kunen , eds., The Kleene Symposium , North-Holland Publishing Company 1980) pp. 123-148. Os famosos "4 princípios de mecanismos [computacionais] de Gandy" incluem o "Princípio IV - O Princípio da Causalidade Local".
  • Yuri Gurevich , Sequential Abstract State Machines Capture Sequential Algorithms , ACM Transactions on Computational Logic, Vol 1, no 1 (julho de 2000), páginas 77-111. Inclui bibliografia de 33 fontes.
  • Kleene C., Stephen (1943). "Predicados e quantificadores recursivos" . American Mathematical Society Transactions . Transações da Sociedade Americana de Matemática, vol. 53, No. 1. 54 (1): 41–73. doi : 10.2307 / 1990131 . JSTOR   1990131 . Reimpresso em The Undecidable , p. 255ff. Kleene refinou sua definição de "recursão geral" e prosseguiu em seu capítulo "12. Teorias algorítmicas" para postular "Tese I" (p. 274); ele mais tarde repetiria esta tese (em Kleene 1952: 300) e a chamaria de "Tese da Igreja" (Kleene 1952: 317) (isto é, a Tese da Igreja ).
  • Kleene, Stephen C. (1991) [1952]. Introdução à Metamatemática (Décima ed.). Editora da Holanda do Norte. Excelente - acessível, legível - fonte de referência para "fundamentos" matemáticos.
  • Knuth, Donald E .. (1973) [1968]. The Art of Computer Programming Second Edition, Volume 1 / Fundamental Algorithms (2ª ed.). Addison-Wesley Publishing Company. O primeiro da famosa série de três textos de Knuth.
  • Lewis, HR e Papadimitriou, CH Elements of the Theory of Computation , Prentice-Hall, Uppre Saddle River, NJ, 1998
  • AA Markov (1954) Teoria dos algoritmos . [Traduzido por Jacques J. Schorr-Kon e equipe do PST] Impressão Moscou, Academia de Ciências da URSS, 1954 [isto é, Jerusalém, Programa de Israel para Traduções Científicas, 1961; disponível no Office of Technical Services, US Dept. of Commerce, Washington] Descrição 444 p. 28 cm. Adicionado tp em Russo Tradução de Obras do Instituto de Matemática, Academia de Ciências da URSS, v. 42. Título original: Teoriya algerifmov. [QA248.M2943 Biblioteca do Dartmouth College. Departamento de Comércio dos EUA, Escritório de Serviços Técnicos, número OTS 60-51085.]
  • Minsky, Marvin (1967). Computation: Finite and Infinite Machines (Primeira edição). Prentice-Hall, Englewood Cliffs, NJ. Minsky expande sua "... ideia de um algoritmo - um procedimento efetivo ..." no capítulo 5.1 Computabilidade, Procedimentos Efetivos e Algoritmos. Máquinas infinitas.
  • Hartley Rogers, Jr , (1967), Theory of Recursive Functions and Effective Computability , MIT Press (1987), Cambridge MA, ISBN   0-262-68052-1 (pbk.)
  • Searle, John (2002). Consciência e linguagem . Cambridge UK: Cambridge University Press. ISBN   0-521-59744-7 .
  • Robert Soare , (1995 para aparecer em Proceedings of the 10th International Congress of Logic, Methodology, and Philosophy of Science , agosto 19-25, 1995, Florença Itália), Computability and Recursion ), na web em ??.
  • Michael Sipser , (2006), Introdução à Teoria da Computação: Segunda Edição , Thompson Course Technology div. da Thompson Learning, Inc. Boston, MA. ISBN   978-0-534-95097-2 .
  • Ian Stewart , Algorithm , Encyclopædia Britannica 2006.
  • Stone, Harold S. Introdução à Organização de Computadores e Estruturas de Dados (edição de 1972). McGraw-Hill, Nova York. Consulte, em particular, o primeiro capítulo intitulado: Algoritmos, máquinas de Turing e programas . Sua sucinta definição informal: "... qualquer sequência de instruções que pode ser obedecida por um robô, é chamada de algoritmo " (p. 4).
  • Peter van Emde Boas (1990), "Machine Models and Simulations" pp 3-66, aparecendo em Jan van Leeuwen (1990), Handbook of Theoretical Computer Science. Volume A: Algorithms & Complexity , The MIT Press / Elsevier, 1990, ISBN   0-444-88071-2 (Volume A)