Prof. Sch\"onhage's Mysterious Machines

• URL: http://arxiv.org/abs/2108.08606v1
• Date: Thu, 19 Aug 2021 10:32:21 GMT
• Title: Prof. Sch\"onhage's Mysterious Machines
• Authors: J.-M. Chauvet
• Abstract summary: We give a simple Sch"onhage Storage Modification Machine that simulates one of the Rule 110 cellular automatons. This provides an alternative construction to Sch"onhage's original proof of the Turing completeness of the eponymous machines.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We give a simple Sch\"onhage Storage Modification Machine that simulates one iteration of the Rule 110 cellular automaton. This provides an alternative construction to Sch\"onhage's original proof of the Turing completeness of the eponymous machines.

Related papers

• Self-Replicating Mechanical Universal Turing Machine [0.0]
  This paper presents the implementation of a self-replicating finite-state machine (FSM) and a self-replicating Turing Machine (TM) using bio-inspired mechanisms.
  arXiv  Detail & Related papers  (2024-09-27T08:28:37Z)
• Simulated Autopoiesis in Liquid Automata [0.0]
  Liquid Automata is a particle simulation with additional rules about how particles are transformed on collision with other particles. Unlike cellular automata, there is no fixed grid or time-step, only particles moving about and colliding with each other in a continuous space/time.
  arXiv  Detail & Related papers  (2024-01-15T21:23:23Z)
• Towards a Self-Replicating Turing Machine [0.0]
  We provide partial implementations of von Neumann's universal constructor and universal copier. Using the same principles, we also construct Turing machines. Our construction allows for mutations if desired, and we give a simple description language.
  arXiv  Detail & Related papers  (2023-06-29T11:50:58Z)
• Token Turing Machines [53.22971546637947]
  Token Turing Machines (TTM) is a sequential, autoregressive Transformer model with memory for real-world sequential visual understanding. Our model is inspired by the seminal Neural Turing Machine, and has an external memory consisting of a set of tokens which summarise the previous history.
  arXiv  Detail & Related papers  (2022-11-16T18:59:18Z)
• What Images are More Memorable to Machines? [87.14558566342322]
  Similar to humans, machines also tend to memorize certain kinds of images, whereas the types of images that machines and humans are different. This work proposes the concept of machine memorability and opens a new research direction at the interface between machine memory and visual data.
  arXiv  Detail & Related papers  (2022-11-14T18:48:08Z)
• On the Intersection of Context-Free and Regular Languages [71.61206349427509]
  We generalize the Bar-Hillel construction to handle finite-state automatons with $varepsilon$-arcs. We prove that our construction leads to a grammar that encodes the structure of both the input automaton and grammar while retaining the size of the original construction.
  arXiv  Detail & Related papers  (2022-09-14T17:49:06Z)
• The Meta-Turing Test [17.68987003293372]
  We propose an alternative to the Turing test that removes the inherent asymmetry between humans and machines. In this new test, both humans and machines judge each other.
  arXiv  Detail & Related papers  (2022-05-11T04:54:14Z)
• Compiling Turing Machines into Storage Modification Machines [0.0]
  It is well known that Sch"onhage's Storage Modification Machines (SMM) can simulate Turing Machines (TM) We propose a simple transformation of TM into SMM, setting the base for a straightforward TM-to-SMM compiler.
  arXiv  Detail & Related papers  (2021-09-28T10:38:05Z)
• Generative Language Modeling for Automated Theorem Proving [94.01137612934842]
  This work is motivated by the possibility that a major limitation of automated theorem provers compared to humans might be addressable via generation from language models. We present an automated prover and proof assistant, GPT-f, for the Metamath formalization language, and analyze its performance.
  arXiv  Detail & Related papers  (2020-09-07T19:50:10Z)
• Populations of Spiking Neurons for Reservoir Computing: Closed Loop Control of a Compliant Quadruped [64.64924554743982]
  We present a framework for implementing central pattern generators with spiking neural networks to obtain closed loop robot control. We demonstrate the learning of predefined gait patterns, speed control and gait transition on a simulated model of a compliant quadrupedal robot.
  arXiv  Detail & Related papers  (2020-04-09T14:32:49Z)
• Reservoir memory machines [79.79659145328856]
  We propose reservoir memory machines, which are able to solve some of the benchmark tests for Neural Turing Machines. Our model can also be seen as an extension of echo state networks with an external memory, enabling arbitrarily long storage without interference.
  arXiv  Detail & Related papers  (2020-02-12T01:45:00Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.