Inicio Noticias Guía teórica del programador - Números trascendentales

Guía teórica del programador – Números trascendentales

Página 1 de 3

El cálculo y los números trascendentales no parecen muy relacionados, pero estos son los números que son irracionales y en principio los más difíciles de calcular. Pero hay excepciones importantes.


Una guía teórica del programador

Ahora disponible como libro de tapa blanda y libro electrónico de Amazon.

Contenido

¿Qué es la tecnología de la información?
Parte I ¿Qué es lo computable?¿Qué es el cálculo? El problema de detener máquinas de estados finitos
Extracto 1: Números gramaticales prácticos, infinito y cálculo de máquina de estado finito
Extracto 1: Números
Extracto 2: Aleph Zero El primer transfinito
Extracto 3: En busca de Aleph-One
Extracto 4: Números trascendentales *** ¡NUEVO!
Complejidad y aleatoriedad de Kolmogorov
Extracto 1: Algoritmo de complejidad de Kolmogorov de su elección Teorema de incompletitud de Gödel Cálculo lambda
Parte II Bits, códigos y lógicaTeoría de la información Teoría de la codificación: división de la lógica de corrección de errores de bits booleanos
Parte III Complejidad Computacional¿Qué tan difícil puede ser?
Extracto 1: De dónde viene la recursividad de Big OS
Extracto 1: ¿Qué es la recursividad?
Extracto 2: Por qué recursión NP versus algoritmos P
Extracto 1: NP y Co-NP
Extracto 2: NP completo

etotheypes

Siempre que comprenda el infinito y el hecho de que hay más de un tipo de infinito, llegará a algunas conclusiones inmediatas e importantes sobre los números: no hay suficientes y demasiados.

Incluido en el capítulo pero no en este extracto

Enteros y racionales Los irracionales La jerarquía de los números Aleph-Zero y todo lo ilimitado e infinito Comparar dimensiones en busca de Aleph-One ¿Qué es más grande que Aleph-Zero? Enumeraciones de «irracionales» finitos pero ilimitados que enumeran los irracionales Aleph-One y más allá

¡Programas insuficientes!

Ahora llegamos al golpe de gracia final para el cálculo y se basa en infinitos. ¿Cuántos programas hay? Cualquier programa es simplemente una secuencia de bits y cualquier secuencia de bits se puede leer como un número binario, un entero binario para ser exactos. Entonces, dado cualquier programa, tiene un número binario correspondiente. Del mismo modo, dado cualquier número binario, puede pensar en él como un programa: puede que no haga nada útil, pero eso no estropea el principio:


Esta correspondencia es un ejemplo de numeración de Gödel y se encuentra a menudo en informática.

Esto significa que el conjunto de programas es igual al conjunto de enteros e inmediatamente nos damos cuenta de que el conjunto de programas es enumerable. Todo lo que tengo que hacer es escribir un ciclo for que cuente de 1 a 2n y tengo todos los programas que se pueden almacenar en n bits. Incluso si deja que este proceso continúe para siempre, la cantidad de programas es enumerable. Es infinito, pero es enumerable y por lo tanto hay programas alef-cero.

Esta es una idea muy extraña. La numeración de Gödel implica que si comienza a generar dicha numeración, eventualmente llegará a un número que es Windows o Linux o Word o cualquier programa que desee nombrar. Esto se ha sugerido ocasionalmente como una metodología de programación, pero solo como una broma.

Puede repetir el argumento con máquinas de Turing en lugar de programas. Cada máquina de Turing se puede representar como una cinta que se inserta en una máquina de Turing universal. La cinta es una secuencia de símbolos que pueden codificarse en binario y leerse como un solo número. Tenemos otra numeración de Gödel y por lo tanto el conjunto de máquinas de Turing es enumerable y si permitimos que la cinta sea finita pero ilimitada hay máquinas de Turing alef-cero. Lo importante es que la cantidad de números irracionales no es enumerable, es alef-uno, lo que significa que hay más números irracionales que programas.

¿Entonces? Piensa en la tarea de calcular todos los números posibles. Es decir, imagina que cada número tiene un programa que lo calcula y lo muestra. Puedes hacerlo con números enteros y puedes hacerlo con racionales, pero no puedes hacerlo con irracionales y hay más números irracionales que programas, así que muchos, de hecho la mayoría, de los números irracionales no tienen programas que los calculen. Tocamos esta idea en el capítulo 3, pero ahora tenemos la ventaja de conocer los órdenes del infinito.

Números como √2, π y e claramente tienen programas que los calculan, por lo que no todos los números irracionales no son computables, pero la gran mayoría no lo son. Para expresarlo de otra manera:


¿Qué significa esto? Bueno, si lo piensas bien, un programa es una construcción relativamente corta y regular y si genera un número irracional, de alguna manera la información en ese número debe ser aproximadamente la misma que la información en el programa que lo genera. Es decir, los números computables son regulares en un sentido complicado, pero un número no computable es tan irregular que no se puede comprimir su estructura en un programa. Esto lleva al estudio de la teoría algorítmica de la información, que es otra área interesante de las ciencias de la computación llena de ideas extrañas y conclusiones aún más extrañas, consulte el Capítulo 7.

Tenga en cuenta que no puede eludir esta conclusión extendiendo de alguna manera la forma en que cuenta los horarios. Por ejemplo, no puede decir que hay un aleph-cero de programas ejecutándose en la computadora A y otro aleph-cero ejecutándose en la computadora B, por lo que tenemos más programas. Esto es incorrecto porque los programas aleph-zero más aleph-zero siguen siendo solo programas aleph-zero. Para evitar el problema, debe inventar una computadora que funcione con números reales como un programa para que haya uno, y probablemente pueda ver el tema circular aquí.

Marc Gomez
Vine a por tabaco y ya me quedé aquí. Cuando no estoy en el sótano de Tecnopasion suelo pasear por las calles de Barcelona.
RELATED ARTICLES