[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Linear bounded automaton

To: "P.H.Welch" <P.H.Welch@xxxxxxxxxx>
Subject: Linear bounded automaton
From: Larry Dickson <tjoccam@xxxxxxxxxxx>
Date: Mon, 17 Jul 2017 10:44:30 -0700
Cc: Occam Family <occam-com@xxxxxxxxxx>
Delivery-date: Mon, 17 Jul 2017 18:44:46 +0100
Dkim-signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=tjoccam-com.20150623.gappssmtp.com; s=20150623; h=mime-version:subject:from:in-reply-to:date:cc :content-transfer-encoding:message-id:references:to; bh=7mZ6fpi0QIDHNrOsNJYxnxz7UHNTh/bQANLTFGSuyKQ=; b=eg7Hf7mHKkmH8o0kVki8LssyrBmqgpuivlkKmZykZiJUK/YycYVWWVPdUEChrtzf3M fmHlG7SKFXlXZTNtVOSo5b4ysgjRvf9BGt/FX70fegdniRircGMpHg5aIoysRvV8m1O0 Y/pKkL1TC6hZT96igfgQ+qq20TqTXgmZ1sQpvAV2ZxCU0BsuQkjIqEw25tvmW2RaHqXH Zl0ZsrQ5I0jUI+WfFEg3+fUCD7Kc6R+gn9KRjIrlDAeaiP4s2WKjppeHa0oBzo7cXLxr bzzXMb8lhJVyZyCAsnm6dIUoZ95Ny4OCmxgOKmWTankVhL0WMG9dyNg6tr7Uto9hKms2 EMMQ==
Envelope-to: ats@xxxxxxxxx
In-reply-to: <E1dX5pG-00057j-KF@beech.kent.ac.uk>
List-help: <mailto:sympa@kent.ac.uk?subject=help>
List-id: <occam-com.kent.ac.uk>
List-owner: <mailto:occam-com-request@kent.ac.uk>
List-post: <mailto:occam-com@kent.ac.uk>
List-subscribe: <mailto:sympa@kent.ac.uk?subject=subscribe%20occam-com>
List-unsubscribe: <mailto:sympa@kent.ac.uk?subject=unsubscribe%20occam-com>
References: <E1dX5pG-00057j-KF@beech.kent.ac.uk>
Reply-to: Larry Dickson <tjoccam@xxxxxxxxxxx>
Sender: occam-com-request@xxxxxxxxxx

Hi all,

This question was probably answered long ago, but I can’t find a reference . . .

Is occam “linear bounded automaton complete”? (Presumably it’s not Turing
complete, because it has finite memory, but neither is anything else, really.
All real implementations of “Turing complete” languages have finite memory.)

Larry

References:
- CPA 2017 (Malta, Aug 20-23) 2nd. Call for Participants
  - From: P.H.Welch

Prev by Date: CPA 2017 (Malta, Aug 20-23) 2nd. Call for Participants
Next by Date: Subscription request to list occam-com
Previous by thread: CPA 2017 (Malta, Aug 20-23) 2nd. Call for Participants
Index(es):
- Date
- Thread