Browse Prior Art Database

On: Simple Machines with an Undecidable Universe Problem

IP.com Disclosure Number: IPCOM000128543D
Original Publication Date: 1977-Dec-31
Included in the Prior Art Database: 2005-Sep-16
Document File: 9 page(s) / 26K

Publishing Venue

Software Patent Institute

Related People

Oscar A. Ibarra: AUTHOR [+3]

Abstract

We show the undecidability of the universe problem for two restricted classes of nondetermiaistic counter machines. These classes are among the simplest known for which the universe problem can be shown unsolvable.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 20% of the total text.

Page 1 of 9

THIS DOCUMENT IS AN APPROXIMATE REPRESENTATION OF THE ORIGINAL.

On: Simple Machines with an Undecidable Universe Problem

by

Oscar A. Ibarra

Computer Science Department 114 Lind Hall Institute of Technology University of Minnesota Minneapolis, Minnesota 55455

Technical Report 77-I6

September 1977

Cover design courtesy of Ruth and Jay Leavitt

Oscar H. Ibarra Department of Computer Science University of Minnesota Minneapolis, Minnesota 55455

Abstract

We show the undecidability of the universe problem for two restricted classes of nondetermiaistic counter machines. These classes are among the simplest known for which the universe problem can be shown unsolvable.

Key words: undecidable, universe problem, halting prod~.em,~counter machines; restricted aondeterminism * This research was supported by the National Science Foundation under Grant Ho. DCR75-17090.

Introduction

The equivalence problem for deterministic finite-turn pushdown machines and for deterministic one-counter machines is decidable [9,10]. Equivalence is also decidable for deterministic two- way mul.ticounter machines whose input and counters are reversal-bounded [6]. On the other hand, the universe problem for the class, C, of nondeterministic one-counter machines whose counter makes at most one reversal is unsolvable [1,2]. This last result clearly illustrates the power of nondeterminism even in simple computing machines. As another example, it is welt' known that relational equivalence is decidable for deterministic generalized sequential machines (gsm's). However, in a recent paper [7], it is shown that relational equivalence is undecidable for e-free nondeterministic gsm's whose input or output alphabet is restricted to one letter. (The unsolvability without the alphabet restriction has been shown earlier in [3].) Here, we consider another instance (the gsm result just mentioned is one) of the following general problem: Suppose a decision problem is un-decidable for a given class of nondeterministic machines but decidable for the deterministic subclass. Find a subclass consisting of machines with "restricted" nondeterminism for which the problem remains unsolvable. We feel that a study of this kind will. give us a better understanding of the true nature of nondeterminism as it relates to decision questions. For a related research effort, one that concerns hierarchies of computations based on the "number"of nondeterministic steps,see [8].

University of Minnesota Page 1 Dec 31, 1977

Page 2 of 9

On: Simple Machines with an Undecidable Universe Problem

In this short note we exhibit two very simple subclasses C1 and C2 of C whose universe problem is unsolvable. The only nondetezminism involved in the operations of the machines comprising C1(C2) consists essentially of deciding when to reverse the counter (when to start using the counter for the first time). We believe that C1 and C2 are among the simplest known classes of machines containing the finite-state acceptors for...