Some properties of four-dimensional parallel Turing machines |
| |
Authors: | Yasuo Uchida Makoto Sakamoto Ayumi Taniue Ryuju Katamune Takao Ito Hiroshi Furutani Michio Kono |
| |
Affiliation: | 1. Department of Business Administration, Ube National College of Technology, 2-14-1 Tokiwadai, Ube, 755-8555, Japan 2. Department of Computer Science and Systems Engineering, University of Miyazaki, Miyazaki, Japan
|
| |
Abstract: | Informally, the parallel Turing machine (PTM) proposed by Wiedermann is a set of identical usual sequential Turing machines
(STMs) cooperating on two common tapes: a storage tape and an input tape. Moreover, STMs which represent the individual processors
of a parallel computer can multiply themselves in the course of computation. On the other hand, during the past 7 years or
so, automata on a four-dimensional tape have been proposed as computational models of four-dimensional pattern processing,
and several properties of such automata have been obtained. We proposed a four-dimensional parallel Turing machine (4-PTM),
and dealt with a hardware-bounded 4-PTM in which each side-length of each input tape is equivalent. We believe that this machine
is useful in measuring the parallel computational complexity of three-dimensional images. In this work, we continued the study
of the 3-PTM, in which each side-length of each input tape is equivalent, and investigated some of its accepting powers. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|