# Smooth relaxation preserving Turing machines

Source: [Smooth relaxation preserving Turing machines](<https://www.sota2.com/research/paper/68fa58251e209131ce9abc75>)

Collection index: [llms.txt](<https://www.sota2.com/research/llms.txt>)

Data updated: 2025-10-25T15:09:36.713Z

Authors: Adrian K. Xu

Published: 2021-06-02T05:46:00.000Z

## Abstract

Clift and Murfet (2019) introduced a naive Bayesian smooth relaxation of Turing machines motivated by work in differential linear logic; this was subsequently used to endow spaces of program codes of bounded length with a smooth manifold structure via the staged-pseudo universal Turing machine introduced by Clift, Murfet and Wallbridge (2021).   In this paper, we give a general construction for simulating n-tape Turing machines on a single tape Turing machine such that the (naive Bayesian) uncertainty is propagated in an equivalent manner. This result suggests a stronger kind of equivalence between single tape and n-tape Turing machines than that established by classical results, however, the clarification of these implications is open to future work. We then construct a pseudo universal Turing machine which similarly preserves the propagation of uncertainty in its simulations, and observe that this gives rise to a particularly natural smooth relaxation of the space of programs.

## Recorded benchmark results

A research result applies to its stated dataset, split, metric and evaluation configuration. Compare like-for-like settings, preserve the metric's unit and direction, and distinguish paper-reported results from independent reproduction. The best result recorded here is not a claim of exhaustive, current global coverage.

## Original sources and implementation

[Original paper](<https://arxiv.org/abs/2106.00956>)

[PDF](<https://arxiv.org/pdf/2106.00956.pdf>)
