Funció computable

Les funcions computables són l'objecte bàsic d'estudi de la teoria de la computabilidad i són, específicament, les funcions que poden ser calculades per una màquina de Turing.

Les funcions computables s'utilisen per a parlar de computabilidad sense fer referència a cap model de computació concret, com les màquines de Turing o les màquines de registre. Qualsevol definició, no obstant, deu fer referència a algun model específic de computació, pero totes les definicions vàlides produïxen la mateixa classe de funcions. Els models particulars de computabilidad que donen lloc al conjunt de funcions computables són les funcions computables de Turings i les funcions recursivas generals.

Abans de la definició precisa de funció computable, els matemàtics utilisaven a sovint el terme informal efectivament calculable. Des de llavors, este terme s'identifica en les funcions computables. Note's que la computabilidad efectiva d'estes funcions no implica que puguen ser eficientemente calculades (és dir, calculades en un temps raonable). De fet, per a algunes funcions efectivament calculables es pot demostrar que qualsevol algoritme que les compute serà molt ineficiente en el sentit de que el temps d'eixecució de l'algoritme aumenta exponencialment (o inclús superexponencialmente) en la llongitut de l'entrada. Els camps de computabilidad factible i complexitat computacional estudien funcions que poden ser computades eficientement.

Segons la tesis de Church-Turing, les funcions computables són exactament les funcions que poden calcular-se utilisant un dispositiu de càlcul mecànic donades cantitats illimitades de temps i espai d'almagasenament. Equivalentement, esta tesis afirma que una funció és computable si i només si té un algoritme. Note's que un algoritme en este sentit s'entén com una seqüència de passos que una persona en temps illimitat i un suministrament illimitat de llapis i paper podria seguir.

Els axioma de Blum poden utilisar-se per a definir una teoria de la complexitat computacional abstracta sobre el conjunt de funcions computables. En la teoria de la complexitat computacional, el problema de determinar la complexitat d'una funció computable es coneix com problema de funció.

Introducció

Les funcions computables són una formalisació de la noció intuïtiva d'algoritme i, segons la tesis de Church-Turing, són exactament les funcions que poden ser calculades en una màquina de Turing. La noció de la computabilidad d'una funció pot ser relativizada a un conjunt arbitrari de número natural A, o equivalentemente a una funció arbitrària f dels naturals als naturals, per mig de màquines de Turing esteses en un oràcul per A o f. Tals funcions poden ser cridades A-computable o f-computable respectivament. Abans de la definició precisa d'una funció computable els matemàtics usaven el terme informal efectivament computable.

Les funcions computables són usades per a discutir sobre computabilidad sense referir-se a cap model de computació concret, com el de la màquina de Turing o el de la màquina de registres. Els axioma de Blum poden ser usats per a definir una teoria de complexitat computacional abstracta sobre el conjunt de funcions computables.

Segons la Tesis de Church-Turing, la classe de funcions computables és equivalent a la classe de funcions definides per funcions recursivas, càlcul lambda, o algoritmes de Markov [1].

Alternativament es poden definir com els algoritmes que poden ser calculats per una màquina de Turing, una màquina de Post, o una màquina de registres.

En teoria de la complexitat computacional, el problema de determinar la complexitat d'una funció computable és conegut com un problema de funcions.

Definició

La computabilidad d'una funció és una noció informal. Una forma de descriure-la és dir que una funció és computable si el seu valor pot obtindre's per mig d'un procediment efectiu. En més rigor, una funció $f:{\mathbb{N}}^k\to \mathbb{N}$ és computable si i només si existix un procediment efectiu que, donada qualsevol k-tupla $𝐱$ d'número natural, produirà el valor $f(𝐱)$. D'acort en esta definició, el restant d'este artícul supon que les funcions computables prenen finitamente molts número natural com a arguments i produïxen un valor que és un únic número natural.

Com a contrapartida a esta descripció informal, existixen múltiples definicions formals i matemàtiques. La classe de funcions computables es pot definir en molts models de computació equivalents, incloent

• Màquina de Turing
• μ-funció recursiva
• Càlcul lambda
• Màquines Post (Màquina Post-Turings i màquines d'etiquetes).
• Màquina de registre

Encara que estos models utilisen diferents representacions per a les funcions, les seues entrades i les seues eixides, existixen traduccions entre dos models qualssevol, per lo que cada model descriu essencialment la mateixa classe de funcions, donant lloc a l'opinió de que la computabilidad formal és al mateix temps natural i no massa estreta. Estes funcions es denominen a voltes "recursivas", en contrast en el terme informal "computables", una distinció derivada d'una discussió de 1934 entre Kleene i Gödel.^p.6

Per eixemple, es poden formalisar funcions computables com funcions μ-recursivas, que són funcions parcials que prenen tuplas finitas de número natural i tornen un únic número natural. Són la classe més chicoteta de funcions parcials que inclou les funcions constant, successora i de proyecció, i és tancada baix composició, recurrencia primitiva i l'operador μ.

Equivalentement, les funcions computables poden formalisar-se com a funcions que poden ser calculades per un agent computacional idealizado com una màquina de Turing o una màquina de registre. Formalment parlant, una funció parcial $f:{\mathbb{N}}^k\to \mathbb{N}$ pot ser calculada si i només si existix un programa d'ordenador en les següents propietats:

1. Si $f(𝐱)$ està definit, llavors el programa terminarà en l'entrada $𝐱$ en el valor $f(𝐱)$ almagasenat en la memòria de l'ordenador.
2. Si $f(𝐱)$ és indefinit, llavors el programa mai termina en l'entrada $𝐱$.

Una funció parcial

$f:\subseteq \mathbb{N}\to \mathbb{N}$

es diu parcialment computable si el gràfic $f$ és un conjumerable. El conjunt de funcions parcialment computables en un paràmetro és normalment escrit ${𝐏}^{(1)}$ o ath> si el número de paràmetros pot deduir-se del context.

Una funció total

$f:\mathbb{N}\to \mathbb{N}$

es diu computable si el gràfic de $f$ és un conjunt recursivo. El conjunt de funcions totalment computables en un paràmetro normalment s'escriu ${𝐑}^{(1)}$ o $𝐑$.

Una funció computable $f$ es diu predicat computable si és una funció en valor booleano, és dir:

$f:\subseteq \mathbb{N}\to \{0,1\}$

Característiques de les funcions computables

Artícul principal → Algoritme.

La característica bàsica d'una funció computable és que deu existir un procediment finito (un algoritme) que diga cóm calcular la funció. Els models de computació enumerats anteriorment donen diferents interpretacions de lo que és un procediment i cóm s'utilisa, pero estes interpretacions compartixen moltes propietats. El fet de que estos models donen classes equivalents de funcions computables prové del fet de que cada model és capaç de llegir i imitar un procediment per a qualsevol dels atres models, de la mateixa manera que un compilador és capaç de llegir instruccions en un llenguage informàtic i emetre instruccions en un atre llenguage.

Enderton [1977] dona les següents característiques d'un procediment per a computar una funció computable; caracterisació similars han segut donades per Turing [1936], Rogers [1967], i uns atres.

• "Deu haver instruccions exactes (és dir, un programa), de llongitut finita, per al procediment". Aixina que, tota funció computable deu tindre un programa finito que descriga completament cóm deu calcular-se la funció. És possible calcular la funció simplement seguint les instruccions; no és necessari endevinar res ni tindre coneiximents especials.
• Si al procediment se li dona una k -tupla x en el domini de f, llavors despuix d'un número finito de passos discrets el procediment deu terminar i produir f(x)". Intuitivament, el procediment procedix pas a pas, en una regla específica per a cobrir qué fer en cada pas del càlcul. Només poden realisar-se un número finito de passos ans que es torne el valor de la funció.
• Si al procediment se li dona una k -tupla x que no està en el domini de f, llavors el procediment podria continuar per a sempre, sense detindre's mai. O podria atollar-se en algun punt (és dir, una de les seues instruccions no pot eixecutar-se), pero no deu pretendre produir un valor per a f en x". Per tant, si alguna volta es troba un valor per a f(x), deu ser el valor correcte. No és necessari que l'agent informàtic distinguixca els resultats correctes dels incorrectes perque el procediment es definix com a correcte si i només si produïx un resultat.

Enderton passa a enumerar varis aclariments d'estos 3 requisits del procediment per a una funció computable:

1. El procediment deu funcionar teòricament per a arguments arbitrariamente grans. No s'assumix que els arguments siguen menors que el número d'àtoms de la Terra, per eixemple.
2. Es requerix que el procediment es detinga despuix d'un número finito de passos per a produir una eixida, pero pot prendre un número arbitrari de passos abans de detindre's. No s'assumix cap llimitació de temps.
3. Encara que el procediment pot utilisar només una cantitat finita d'espai d'almagasenament durant un càlcul en èxit, no hi ha llímit en la cantitat d'espai que s'utilisa. Se supon que es pot proporcionar espai d'almagasenament adicional al procediment sempre que este ho solicite.

En resum, des d'este punt de vista, una funció és computable si:

• donada una entrada del seu domini, possiblement contant en un espai d'almagasenament illimitat, pot donar l'eixida corresponent seguint un procediment (programa, algoritme) que està format per un número finito d'instruccions exactes no ambigües;
• Llavors torna dit resultat (es deté) en un número finito de passos; i
• si se li dona una entrada que no està en el seu domini, o be mai es deté o es queda atollat.

El camp de la complexitat computacional estudia funcions en llímits prescrits en el temps i/o espai permesos en una computació exitosa.

Conjunts i relacions computables

Un conjunt A d'número natural es diu computable (sinònims: recursivo, decidible) si existix una funció computable, total f} tal que per a qualsevol número natural n, f(n) = 1 si n està en A i f(n) = 0 si n no està en A.

Un conjunt d'número natural es diu computablemente enumerable (sinònims: recursivamente enumerable', semidecidible) si existix una funció computable f} tal que per a cada número n, f(n) està definida si i només si. n està en el conjunt. Aixina, un conjunt és computablemente enumerable si i només si és el domini d'alguna funció computable. La paraula enumerable s'utilisa perque els següents són equivalents per a un subconjunt no buit B dels número natural:

• B és el domini d'una funció computable.
• B és el ranc d'una funció total computable. Si B és infinit llavors es pot supondre que la funció és inyectiva.

Si un conjunt B és el ranc d'una funció f llavors la funció pot vore's com una enumeració de B, perque la llista f(0), f(1), ... inclourà cada element de B.

Ya que cada relació matemàtica sobre els número natural pot identificar-se en un conjunt corresponent de seqüències finitas d'número natural, les nocions de relació computable i relació computablemente enumerable poden definir-se a partir de les seues anàlogues per a conjunts.

Llenguages formals

Artícul principal → Llenguage formal.

En Teoria de la computabilidad en informàtica, és comuna considerar llenguages formals. Un alfabet és un conjunt arbitrari. Una paraula en un alfabet és una seqüència finita de símbols de l'alfabet; el mateix símbol pot usar-se més d'una volta. Per eixemple, les cadenes binarias són exactament les paraules de l'alfabet 0, 1. . Un llenguage és un subconjunt de la colecció de totes les paraules d'un alfabet fix. Per eixemple, la colecció de totes les cadenes binarias que contenen exactament 3 uns és un llenguage sobre l'alfabet binario.

Una propietat clau d'un llenguage formal és el nivell de dificultat necessari per a decidir si una paraula donada està en el llenguage. Deu desenrollar-se algun sistema de codificació que permeta a una funció computable prendre com a entrada una paraula arbitrària del llenguage; açò sol considerar-se rutina. Un llenguage es diu computable (sinònims: recursivo, decidible) si existix una funció computable f tal que per a cada paraula w sobre l'alfabet, f(w) = 1 si la paraula està en la llengua i f(w) = 0 si la paraula no està en el llenguage. Aixina, un llenguage és computable només en el cas de que existixca un procediment capaç de dir correctament si paraules arbitràries estan en el llenguage.

Un llenguage és computablemente enumerable (sinònims: recursivamente enumerable, semidecidible) si existix una funció computable f tal que f(w) està definida si i només si la paraula w està en el llenguage. El terme enumerable té la mateixa etimologia que en conjunts computablemente enumerables d'número natural.

Comentaris

A voltes, per raons de claritat, s'escriu una funció computable com

$g:\subseteq {\mathbb{N}}^k\to \mathbb{N}$

Es pot fàcilment codificar g en una nova funció

$f:\subseteq \mathbb{N}\to \mathbb{N}$

usant una funció de parells.

Eixemples

Les següents funcions són computables:

• Cada funció en un domini finito; per eixemple, qualsevol seqüència finita d'número natural.
• Cada funció constant f : N^k → N', f(n₁,...n_k) := n.
• Suma f : N² → N', f(n₁,n₂) := n₁ + n₂.
• El màxim comú divisor de dos números
• El coeficient de Bézout de dos números
• El factor primer més chicotet d'un número.

Si f i g són computables, llavors també ho són: f + g, f * g, $f\circ g$ si f és unaria, max(f,g), min(f,g), arg maxPlantilla:Mset i moltes més combinacions.

Els següents eixemples ilustren que una funció pot ser computable encara que no se sàpia qué algoritme la computa.

• La funció f tal que f(n) = 1 si hi ha una seqüència de a lo manco n cincos consecutius en l'expansió decimal de π, i f(n) = 0 en cas contrari, és computable. (La funció f és la funció constant 1, que és computable, o be existix un k tal que f(n) = 1 si n < k i f(n) = 0 si n ≥ k. Tota funció d'este tipo és computable. No se sap si hi ha séries arbitrariamente llargues de cincos en l'expansió decimal de π, aixina que no sabem quin d'eixes funcions és f. No obstant, sabem que la funció f deu ser computable).
• Cada segment finito d'una seqüència no computable d'número natural (com la funció del castor ocupat Σ) és computable. Per eixemple, per a cada número natural n, existix un algoritme que calcula la seqüència finita Σ(0), Σ(1), Σ(2), ..., Σ(n) - en contrast en el fet de que no hi ha algoritme que calcula la sancera seqüència Σ, és dir, Σ(n) para tots els n. Per lo tant, "Imprimir 0, 1, 4, 6, 13" és un algoritme trivial per a calcular Σ(0), Σ(1), Σ(2), Σ(3), Σ(4); De la mateixa manera, per a qualsevol valor donat de n, tal algoritme trivial existix (encara que mai puga ser conegut o produït per ningú) per a calcular Σ(0), Σ(1), Σ(2), . .., Σ(n).
• Funció constant f : N^k→ N, f(n₁,...n_k) := n

• Adició f : N²→ N, f(n₁,n₂) := n₁ + n₂

Propietats

• El conjunt de les funcions computables és numerable.

• Si $f$ i $g$ són funcions computables llavors $f+g$, $f\cdot g$ i $f\circ g$ són funcions computables.

• Les funcions computables són definibles aritméticament.

• Una funció en valor booleano $f$ és un predicat computable si i només si el llenguage $\{x\in {\Sigma }^{*}:f(x)=1\}$ és recursivo.