Message Boards Message Boards

GROUPS:

Three questions about the principles of rewrite / substitution system

Posted 2 months ago
655 Views
|
3 Replies
|
0 Total Likes
|

Hi community,

This is my first post related to physics project. It is very exciting and approachable for me as a thinker with programming background and strong mathematical and philosophical interest.

1) Is it possible to make a find and replace substitution algorithm for a Quantum Computer, operate and compute hypergraphs in a quantum world rather than in traditional computer environments?

2) Are there any fundamental differences between the Lambda Calculus variable substitution and rewrite process presented in the simpler string substitution and the hypergraph rewrite systems?

3) Is there some physical counterpart for the rewrite/substitution system i.e. what is the argumentation that rewrite is something that is supposed to go on behind the physical laws and principles and forces, is that the only computational model for doing so?


I found something related to QC on Wolfram physics project worklog videos and documents, not exactly answering my first question, but somewhere there: https://youtu.be/Uj1vLMRkoDU

https://www.wolframphysics.org/technical-introduction/potential-relation-to-physics/basic-concepts-of-quantum-mechanics/

In one video worklog (about category theory, I think) Lambda Calculus was shortly appearing there, but conversation jumped to other topics quickly.

3 Replies

In EP380 there is also a short mention about Lambda Calculus and variable renaming: https://youtu.be/z7boq5L0qZc?t=3413 Looking forward the joined discussion with LC expert in future, it will be super exciting.

1) Is it possible to make a find and replace substitution algorithm for a Quantum Computer, operate and compute hypergraphs in a quantum world rather than in traditional computer environments?

Answer: a qubit is essentially a hypergraph, where each hyper-edge (including the empty set), is labeled by a complex number. Some restrictions concerning normalization should be added, but this is easy. So, the answer to your question is "yes", but this is independent of the Wolfram Model: it is just basic quantum information theory.

2) Are there any fundamental differences between the Lambda Calculus variable substitution and rewrite process presented in the simpler string substitution and the hypergraph rewrite systems?

Answer: Because the untyped lambda calculus is Turing-complete, it can simulate the hypergraph rewrite system.

3) Is there some physical counterpart for the rewrite/substitution system i.e. what is the argumentation that rewrite is something that is supposed to go on behind the physical laws and principles and forces, is that the only computational model for doing so?

Answer: An example of the physical counterpart of rewrite/substitution is Susskind's multiway system of small unitaries: Manuscript, Video

Thank you, José. I suspected 2, but 1 and especially 3 was the most interesting follow up! -Marko

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