Show simple item record

dc.contributor.authorSánchez Ortega, Ana
dc.contributor.authorIbáñez Martínez-Conde, Jesús
dc.contributor.authorIrastorza Goñi, María Aránzazu
dc.date.accessioned2016-05-23T09:58:28Z
dc.date.available2016-05-23T09:58:28Z
dc.date.issued2010
dc.identifier.urihttp://hdl.handle.net/10810/18294
dc.description.abstractLa Teoría de la Computabilidad es una disciplina encuadrada en la Informática Teórica que tiene como objetivo establecer los límites lógicos que presentan los sistemas informáticos a la hora de resolver problemas mediante el diseño de algoritmos. Estos resultados proporcionan importantes herramientas que se utilizan para demostrar tanto la computabilidad como la incomputabilidad de muchas funciones relevantes. Los primeros problemas incomputables que se encontraron lo fueron allá por la década de los años 30. El problema de parada es el primer y más conocido ejemplo de problema no resoluble mediante técnicas algorítmicas: ningún ordenador, por muy potente que sea, puede anticipar el comportamiento de los programas en ejecución, y decidir de antemano si terminarán o no. Este problema nos proporciona un soporte intuitivo para anticipar la incomputabilidad de otros problemas relacionados y un procedimiento para resolverlos: el método de diagonalización. Sin embargo para determinados problemas también incomputables hay que recurrir a otros métodos. Este texto incluye una descripción de otra técnica básica de Teoría de la Computabilidad: la Reducción. La base del método estriba en demostrar que ciertos pares de problemas están fuertemente relacionados de modo que si el segundo tiene solución algorítmica entonces el primero debe tenerla necesariamente también. Esta relación se establece por medio de funciones transformadoras computables, que permiten convertir de manera automática las instancias positivas del primer problema en instancias positivas del segundo. Esta técnica se utiliza muy a menudo porque resulta comparativamente más sencilla que la diagonalización, ya que en general requiere menos esfuerzo para demostrar la incomputabilidad de un mismo problema.es
dc.language.isospaes
dc.relation.ispartofseriesUPV/EHU/LSI/TR;07-2010
dc.rightsinfo:eu-repo/semantics/openAccesses
dc.subjectcomputabilidades
dc.subjectindecibilidades
dc.subjecttécnica de reducciónes
dc.titleEl método de reducción en Teoría de la Computabilidades
dc.typeinfo:eu-repo/semantics/reportes
dc.departamentoesLenguajes y sistemas informáticoses_ES
dc.departamentoeuHizkuntza eta sistema informatikoakes_ES


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record