Exact integer multiplication with saving κ = 0.00363797977
OpenIntMul.Kappa.conditional_kappa_00363797977_pr7113There exists one deterministic multitape Turing machine, with fixed finite alphabet and tape count, that correctly multiplies every pair of n-bit inputs for all n ≥ 1, with worst-case time O(n L(n)^(1−0.00363797977)), where L(n) = max(ceil(log₂ n), 1). This is the full bound with no assumed algorithmic or analytic framework. Its proof is Open.
import Definitions.Def_IntMul_MultitapeModel
namespace IntMul.Kappa theorem conditional_kappa_00363797977_pr7113 : KappaBound (0.00363797977 : ℝ) := by sorry end IntMul.Kappa
Read-back
What the Lean code literally says, in plain math · claude-sonnet-5-5
Read-back de IntMul.Kappa.conditional_kappa_00363797977_pr7113
L'énoncé affirme, sans aucune hypothèse supplémentaire, que la propriété est vraie pour le réel (littéral décimal, interprété comme un réel).
Machines. Une machine de Turing déterministe à rubans, avec , se compose d'un alphabet fini contenant cinq symboles deux à deux distincts (le blanc , le symbole de début , , , ), d'un ensemble fini d'états avec un état initial et un état d'arrêt différents, et d'une fonction de transition . Sur une cellule portant , la machine réécrit et ne va pas à gauche ; n'est jamais écrit ailleurs ; dans l'état d'arrêt la configuration est figée ; le ruban (entrée) n'est jamais modifié. Le ruban est le ruban de sortie, les autres sont des rubans de travail, tous infinis à droite.
Configuration initiale sur ( listes de bits) : état initial, ruban d'entrée , autres rubans , têtes en cellule .
Arrêt avec sortie. Après exactement pas, l'état est l'état d'arrêt et le ruban de sortie contient exactement ; les autres rubans ne sont pas contraints.
Fonctions auxiliaires. est l'entier écrit en binaire par (bit de poids fort en premier). est la liste des bits de (poids fort en premier, troncature modulo ). , donc .
Borne de temps. signifie : il existe une machine à rubans telle que (1) pour tout et toutes listes de bits de longueur , arrête sur avec la sortie ; (2) il existe et tels que, pour tout , cet arrêt a lieu en au plus pas. La même machine convient pour tous les ; alphabet, états et nombre de rubans sont libres mais finis.
Borne . est avec (puissance réelle).
Énoncé complet. Il existe une machine de Turing déterministe multiruban et des constantes , telles que calcule le produit sur bits pour tout et le fait en au plus pas pour tout . C'est une affirmation inconditionnelle d'existence, sans autre paramètre ; la preuve est laissée en sorry.
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.