Every discrete input machine is linearly simulatable

摘要

This paper extends the work of Herman (1971) to show that all discrete input sequential machines (whether finite or infinite state) are linearly simulatable over fields of infinite characteristic. Since this permits the computation of nonrecursive functions, it is concluded that allowing nonlinear output decoding with infinite state linear machines leads to a triviality (as opposed to the case of finite state linear machines where it does not).