Cornell University
Library
Cornell UniversityLibrary

eCommons

Help
Log In(current)
  1. Home
  2. Cornell Computing and Information Science
  3. Computer Science
  4. Computer Science Technical Reports
  5. An Improved Simulation Result for Ink Bounded Turing Machines

An Improved Simulation Result for Ink Bounded Turing Machines

File(s)
78-348.pdf (456.12 KB)
78-348.ps (249.09 KB)
Permanent Link(s)
https://hdl.handle.net/1813/7466
Collections
Computer Science Technical Reports
Author
Melville, Robert C.
Abstract

A (one tape, deterministic) Turing machine is $f(n)$ ink bounded if the machine changes a symbol of its work tape at most $O(f(n))$ times while processing any input of length $n$. The main result of our paper is the construction of an "ink efficient" universal machine which, for any $f(n)$ ink bounded machine $M$ and input $x$, can simulate the processing of $M$ on $x$ or detect that $M$ is looping infinitely on input $x$. The universal machine requires $O(f(n)^{1+\epsilon)$ ink for this simulation where $\epsilon$ is an arbitrarily small positive number. As a corollary, we establish that the class of all $f(n)$ ink bounded computations is properly contained in the class of all $g(n)$ ink bounded computations assuming $\stackrel{inf}{n \rightarrow \infty} \frac{f(n)^{1+\varepsilon}}{g(n)} = 0$ and a technical condition on g.

Date Issued
1978-08
Publisher
Cornell University
Keywords
computer science
•
technical report
Previously Published as
http://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.cs/TR78-348
Type
technical report

Site Statistics | Help

About eCommons | Policies | Terms of use | Contact Us

copyright © 2002-2026 Cornell University Library | Privacy | Web Accessibility Assistance