Curso 10 · intermedio · ~6 h
Computación y sus límites
Autómatas finitos, máquinas de Turing, castores afanosos y lo que ningún programa puede decidir
Construyes un autómata finito que decide si un número binario es múltiplo de 3, demuestras con el palomar lo que no puede contar, programas un simulador de máquinas de Turing con su diagrama espacio-tiempo, cazas castores afanosos por fuerza bruta y terminas frente al problema de la parada, Collatz y los sistemas de etiquetas de Post.
Qué vas a construir
- Autómatas finitos deterministas y un reconocedor de múltiplos de 3
- El argumento del palomar contra aⁿbⁿ, ejecutado
- Un simulador de máquinas de Turing con cinta infinita
- Una máquina que suma 1 en binario y su diagrama espacio-tiempo
- Castores afanosos: BB(2), BB(3), BB(4) y la enumeración completa de 2 estados
- Diagonalización y semidecisión de la parada
- Collatz y un sistema de etiquetas que la computa
Prerrequisitos
- JavaScript básico (objetos, strings)
- Curiosidad por la lógica; no hace falta teoría previa
Temario
Unidad 01
Memoria finita
Construyes
runDFA()traceDFA()drawTrace()pigeonholeWitness()fooled()Cierra con reflexión
Lo que cabe en una cantidad fija de memoria
Unidad 02
Máquinas de Turing
Construyes
tmStep()parseTM()runTM()tapeString()drawSpaceTime()countOnes()busyBeaverStats()enumerate2State()Cierra con reflexión
¿Qué es un procedimiento efectivo?
Unidad 03
Los límites
Construyes
diagonalize()inTable()parseTM()tmStep()runTM()tapeString()haltsWithin()collatzSteps()collatzOrbit()tagSystem()collatzByTag()Cierra con reflexión
La diagonal: lo que ningún programa puede decidir
Al terminar
Laboratorio libre
Un sandbox que se arma con tus funciones del curso (las que pasaron los checks) y retos abiertos sin guion. Para ver versiones terminadas, visita Kósmos Interactivo (kosmos-interactivo.vercel.app).