TTL computing

From: blstuart_at_bellsouth.net <(blstuart_at_bellsouth.net)>
Date: Sun Apr 14 18:37:52 2002

In message <E16wOlk-0000BS-00_at_leng.cold.waste>, Thilo Schmidt writes:
>To get the hierarchy ("<=>" means equivalent):
>
>FSMs <=> regular languages <=> primitive recursive functions
>
>PDAs <=> context free languages <=> partial recursive functions
>
>Turing Machines <=> context sensitive languages <=> computable functions

One quibble:

Linearly bounded automata <=> context sensitive languages

Turing Machines <=> phrase structured languages


Of course, if you want to get exotic, there's probabilistic
automata. Throw in rules for creating new states and
updating probabilities based on experience and you've
got the machine learning research in my dissertation.

Brian L. Stuart
Received on Sun Apr 14 2002 - 18:37:52 BST