TCSLib

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

Theorem 179.1 Existence of a time bound for a computing machine
✓

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.

Definition 179.2 Computable string function
✓
#

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].