Definition talk:Abstract Machine

I would like to give this a much more rigorous definition, to make it usable in proofs directly. Specifically, I want to define an abstract machine as $\tuple {S, \vdash}$ where:

$S$ is a set of configurations

${\vdash} \subset S \times S$ is the transition relation

The key question about abstract machines is, given $a, b \in S$, is whether there a sequence $s_0, s_1, \dotsc, s_n$ such that:

$a = s_0 \vdash s_1 \vdash \dotso \vdash s_n = b$

all hold.

I would also like to define a deterministic abstract machine as one where $\vdash$ is many-to-one.

I far as I know, these definitions are not standard, and I don't even know if they are present in literature, but it would provide a very useful framework for analyzing things like oracle machines.

Is this acceptable? --CircuitCraft (talk) 17:55, 20 April 2023 (UTC)

Not sure. Everything we have is to be sourced (yes I know we're not perfect, it's an aim). Something as clearly venturesome as this when we don't yet know quite what we're talking about would not be a good move in my book.

The approach which has been more than a little successful in the past is to follow the thread of a source work as closely as possible.

If you care to explore your ideas in detail, feel free to use a subpage/substructure from your own user page (see for example the meticulous approach of User:Leigh.Samphier.

As and when you encounter citations (all of which should be traceable to hardcopy, or an established online successor of the traditional mathematical journals, or one of the accepted reference websites) you can then work on migrating it into the main body of the database.

Please carry on the good work. --prime mover (talk) 19:42, 20 April 2023 (UTC)

Incidentally, I fully plan getting back to the Hopcroft and Ullman in due course, but got sidetracked with some physics which alerted me to how poor our coverage of three dimensional geometry is. But I find that very hard work. --prime mover (talk) 19:46, 20 April 2023 (UTC)