179 Complexity — Computable
179.1 Overview
This module defines the machine-independent notion of a computable total string function [AB09, §1.4, p. 20] — some finite binary Turing machine computes it, with no time constraint — and proves the bridge back to the time-bounded notion: any machine that computes a function without a stated time bound in fact computes it within some time bound.
179.2 Declarations
Let \(\Sigma \) be a finite alphabet, let \(M\) be a finite Turing machine over \(\Sigma \), and let \(f\) be a total function from strings over \(\Sigma \) to strings over \(\Sigma \). If \(M\) computes \(f\) — on every input \(x\) it halts, after some finite number of steps, with \(f(x)\) on its output tape, with no stated time bound — then there exists a function \(T : \mathbb {N} \to \mathbb {N}\) such that \(M\) computes \(f\) within time \(T\), i.e. on every input \(x\) the machine \(M\) halts with output \(f(x)\) within \(T(\left\lvert x\right\rvert )\) steps, where \(\left\lvert x\right\rvert \) is the length of \(x\). No monotonicity, positivity, or constructibility of \(T\) is claimed.
A total function \(f\) on bit strings (from \(\{ 0,1\} ^*\) to \(\{ 0,1\} ^*\)) is computable if there exists a finite Turing machine over the binary alphabet that computes \(f\): on every input \(x\) it halts, after some finite number of steps, with \(f(x)\) on its output tape. No time constraint is imposed [AB09, §1.4, p. 20].