Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Posting-Version: version B 2.10.1 6/24/83; site sbcs.UUCP
Path: utzoo!linus!philabs!sbcs!debray
From: debray@sbcs.UUCP (Saumya Debray)
Newsgroups: net.math
Subject: logic question
Message-ID: <557@sbcs.UUCP>
Date: Sat, 24-Dec-83 13:00:40 EST
Article-I.D.: sbcs.557
Posted: Sat Dec 24 13:00:40 1983
Date-Received: Sun, 25-Dec-83 04:24:35 EST
Distribution: net.all
Organization: SUNY at Stony Brook
Lines: 24

:
Given two logics A and B, and A is more expressive than B:

(1) if A and B are both decidable, does the fact that A is more
    expressive than B imply that A's decision procedure is harder
    (i.e. of higher complexity) than B's?

(2) if A and B are not both decidable, does the fact that A is more
    expressive than B imply that A is of a higher unsolvability degree
    than B?


-- 

Saumya Debray
SUNY at Stony Brook

		{floyd, bunker, cbosgd, mcvax, cmcl2}!philabs!
							      \
	Usenet:						       sbcs!debray
							      /
		   {allegra, teklabs, hp-pcd, metheus}!ogcvax!

	CSNet: debray@suny-sbcs@CSNet-Relay