Factorization and optimal algorithms in the Turing machine model

In this work, the input space (the set of all finite words) \(\Sigma^*\) is endowed with the discrete topology \(\tau_d = \mathcal{P}(\Sigma^*)\). A generalisation of the Hausdorff axiom is introduced — dynamically distributed Hausdorffness (DDH), which does not require an a priori assumption of point isolation. Based on the notions of dynamic reachability \(\sim\) and a reference state \(S^*\), the dynamic rank operator \(\eta\) is introduced. DDH together with the dynamic rank operator \(\eta\) make it possible to decompose formally connected graphs or other systems into independent components. Algebraic obstacles such as the unsolvability of a Galois group are isolated and handled as separate components. The origin of singularities and exponential explosions is demonstrated: they arise as singularities when attempting to “glue” isolated points. The discretisation operators \(\Delta_\varepsilon\) and \(\Delta_\mu\) remove these singularities. У цій роботі простір входів(множина всіх скінченних слів) \(\Sigma^*\) наділяється дискретною топологією \(\tau_d = \mathcal{P}(\Sigma^*)\). Вводиться узагальнена аксіома Гаусдорфа — динамічно розподілена гаусдорфовість (ДРГ), яка не потребує апріорного припущення про ізольованість точок. На основні поняття динамічної досяжності $\sim$ та еталонного стану $S^*$ введено оператор динамічного рангу $\eta$. ДРГ разом із оператором динамічного рангу $\eta$ дають змогу розкладати формально зв'язні графи або інші системи на незалежні компоненти. Алгебраїчні перешкоди як нерозв'язність групи Галуа ізолюються та обробляються як окремі компоненти. Продемонстровано походження сингулярностей та експоненційних вибухів: вони виникають як сингулярності при спробі «склеювання» ізольованих точок. Оператори дискретизації \(\Delta_\varepsilon\) та \(\Delta_\mu\) усувають ці сингулярності.