Message Boards Message Boards

0
|
2108 Views
|
5 Replies
|
2 Total Likes
View groups...
Share
Share this post:

Experiments with a boolean rewriting system

Posted 1 year ago

Hi, I'm new to this forum and to Wolfram Notebooks. Even the Wolfram Language is new to me. I'm working on a Notebook about a substitutional rewriting system for Boolean algebra. The main idea is to apply a rewriting system for Boolean expressions where the substitution for variables is initially done. For example an expression like: And[x, Or[z, y]] becomes through substitution with x = 1, y = 0 and z = 1: And[1, Or[1, 0]] and then a term rewriting system iterates on this expression until no more changes are made.

The rationale for this approach is that rewriting systems in general tend to produce iterations that become very large, and by first applying substitution for the variables with constant values the iterations in the Boolean case quickly generate a reduction to either True or False (0 or 1). When the MultiwayCombinator is set to "Sequential" mode the iterations reduce faster, yet the multiway approach seems to produce the exact same results even though it produces longer expressions in the chain of rewriting.

If you have further ideas, or know of a similar approach already been made, feel free to give me feedback. And comments in general about this approach are also appreciated since this is for me an experimental approach.

POSTED BY: Anders Lindman
5 Replies

I have now done some more work. I'm not an expert in the area of term rewriting systems and have used ChatGPT to produce some of the text. Attached is the current state.

POSTED BY: Anders Lindman

What is the advantage to this over simply letting the expressions evaluate? Is the purpose to visualize a specific evaluation path?

POSTED BY: Daniel Lichtblau

The purpose is to significantly reduce the explosion of term replacement systems and approaches like SK combinators. I don't know yet if this is a valid method or something that could have benefits over simply just evaluating the expressions in a traditional sense.

The basic idea is that it will provide a simple mechanism for parallel computation. I don't know yet if this can be achieved within a single term rewriting system or if it's easier to just run several replacement systems of this kind in parallel and then combine the results.

Also, I don't know how things like loops and recursion could be implemented, or if that can be replaced by ordinary boolean expressions in a simple or at least in a feasible way.

POSTED BY: Anders Lindman

Welcome to Wolfram Community!
Please provide your efforts in the form of the Wolfram Language code. This will make it easier for other members to understand you. Check several methods available to include your code in the rules http://wolfr.am/READ-1ST

POSTED BY: Moderation Team

I have just started. Attached is one of my simple Notebooks. This is of course a trivial example. The idea is to extend it to allow parallel computation in a more general sense.

POSTED BY: Anders Lindman
Reply to this discussion
Community posts can be styled and formatted using the Markdown syntax.
Reply Preview
Attachments
Remove
or Discard

Group Abstract Group Abstract