b'\n_START_ARTICLE_\nRedu\xc3\xa7\xc3\xa3o de Turing\n_START_SECTION_\nRela\xc3\xa7\xc3\xa3o de completude de Turing \xc3\xa0 universalidade computacional\n_START_PARAGRAPH_\nTuring completude, como j\xc3\xa1 foi definido acima, corresponde apenas parcialmente a Turing completude no sentido dado na computa\xc3\xa7\xc3\xa3o universal. Especificamente, uma m\xc3\xa1quina de Turing \xc3\xa9 uma m\xc3\xa1quina de Turing universal sse o problema da parada(i.e., o conjunto de entrada para cada eventual parada) \xc3\xa9 uma redu\xc3\xa7\xc3\xa3o muitas para uma. Assim, uma condi\xc3\xa7\xc3\xa3o necess\xc3\xa1ria, mas insuficiente para uma m\xc3\xa1quina ser computacionalmente universal, \xc3\xa9 que problema da parada seja Turing-completa para o conjunto  de conjuntos recursivamente enumer\xc3\xa1veis\xe2\x80\x8b\xe2\x80\x8b.\n_START_SECTION_\nExemplos\n_START_PARAGRAPH_\nDeixando  denotar o conjunto de valores de entrada para o qual a m\xc3\xa1quina de Turing com \xc3\xadndices e p\xc3\xa1ra. Depois os conjuntos  e  s\xc3\xa3o Turing equivalente (aqui  denota uma fun\xc3\xa7\xc3\xa3o de emparelhamento eficaz). A redu\xc3\xa7\xc3\xa3o mostrada  pode ser constru\xc3\xadda usando o fato de . Dado um par , um novo \xc3\xadndice   pode ser constru\xc3\xaddo usando o teorema Smn de tal forma que o programa codificado por  ignora sua entrada e apenas simula o c\xc3\xa1lculo da m\xc3\xa1quina com o \xc3\xadndice e da entrada n.Em particular, a m\xc3\xa1quina com o \xc3\xadndice  ou p\xc3\xa1ra em todas as entrada ou n\xc3\xa3o p\xc3\xa1ra em nenhuma entrada. Assim,  v\xc3\xa1lidos para todos os e e n. Porque a fun\xc3\xa7\xc3\xa3o i \xc3\xa9 comput\xc3\xa1vel, isso mostra . As redu\xc3\xa7\xc3\xb5es apresentadas aqui n\xc3\xa3o s\xc3\xa3o apenas redu\xc3\xa7\xc3\xb5es de Turing, mas redu\xc3\xa7\xc3\xb5es de muitos para um, discutidos abaixo.\n_START_SECTION_\nO uso da redu\xc3\xa7\xc3\xa3o\n_START_PARAGRAPH_\nUma vez que cada redu\xc3\xa7\xc3\xa3o de um conjunto B para um conjunto A tem que determinar se um \xc3\xbanico elemento est\xc3\xa1 em A em um n\xc3\xbamero de passos finitos, s\xc3\xb3 se pode fazer um n\xc3\xbamero finito de consultas aos membros do conjunto B. Quando a quantidade de informa\xc3\xa7\xc3\xb5es sobre o conjunto B, usada para computar um \xc3\xbanico bit de A \xc3\xa9 detalhada, ela \xc3\xa9 feita precisamente pela fun\xc3\xa7\xc3\xa3o de uso. Formalmente, o uso de uma redu\xc3\xa7\xc3\xa3o \xc3\xa9 a fun\xc3\xa7\xc3\xa3o que envia um n\xc3\xbamero natural n para o maior n\xc3\xbamero natural m cuja participa\xc3\xa7\xc3\xa3o est\xc3\xa1 no conjunto B e foi consultada pela redu\xc3\xa7\xc3\xa3o, enquanto determinada a participa\xc3\xa7\xc3\xa3o de n em A.\n_START_SECTION_\nRedu\xc3\xa7\xc3\xb5es fracas\n_START_PARAGRAPH_\nDe acordo com a Tese de Church-Turing, uma redu\xc3\xa7\xc3\xa3o de turing \xc3\xa9 a forma mais geral de uma redu\xc3\xa7\xc3\xa3o efetivamente calcul\xc3\xa1vel. No entanto, as redu\xc3\xa7\xc3\xb5es mais fracas tamb\xc3\xa9m s\xc3\xa3o consideradas. Um conjunto A \xc3\xa9 dito como aritm\xc3\xa9tico em B se A \xc3\xa9 defin\xc3\xadvel pela f\xc3\xb3rmula aritm\xc3\xa9tica de Peano sendo B como um par\xc3\xa2metro. O conjunto A \xc3\xa9 hiper aritm\xc3\xa9tico em B se existe um ordinal recursivo \xce\xb1 tal como A \xc3\xa9 comput\xc3\xa1vel de , o \xce\xb1-iterado salto Turing de B. A no\xc3\xa7\xc3\xa3o de universo construt\xc3\xadvel \xc3\xa9 um importante no\xc3\xa7\xc3\xa3o de retutibilidade na teoria dos conjuntos.'