All Questions
Tagged with cellular-automata turing-machines
9 questions
0
votes
1
answer
587
views
What are the differences/relationship between 2D Turing Machines and Cellular Automata
I have been reading up on 2D Turing machines on wolframscience and I am kind of confused about what exactly is the relationship between 2D Turing machines (like Paterson's worm and Langton's Ant) and ...
- 103
0
votes
2
answers
127
views
Is there any model of Game of Life compatible with hypercomputation?
I found a question in Mathematics Stack Exchange which asks a very similar question
(https://math.stackexchange.com/questions/1023812/hypercomputation-higher-dimensional-variants-of-conways-game-of-...
2
votes
0
answers
57
views
In what sense can a cellular automaton be Turing complete? [duplicate]
The rule 110 cellular automaton is known (or claimed) to be Turing complete. But what exactly does it mean?
I do know what Turing completeness mean. Roughly speaking a language is Turing complete if ...
- 121
4
votes
2
answers
3k
views
Turing-completeness, Conway's Game of Life and Logical Gates
I was recently given an assignment at university asking me to discuss the universal computational capability of Conway's Game of Life.
I'm not required to actually build up a Universal Turing machine ...
- 215
2
votes
1
answer
27
views
How to identify strongly confluent cellular automatas?
Lets represent a class of cellular automata as a finite, unidimensional bit array state : [Bit], plus a rewrite rule ...
- 4,159
2
votes
1
answer
427
views
Does solving mathematical equations with Cellular Automata structures means it is universal?
I'm working on a research about Elementary Cellular Automata (ECA), and i found a method to build a system that can solve mathematical equations by using a specific cellular automaton structure.
The ...
1
vote
0
answers
676
views
How to simulate a cellular automaton via a Turing machine
It is rather easy to see that every cellular automaton can be simulated by a Turing machine: We can simulate a cellular automaton with an appropriate C program and every C program can be simulated by ...
- 451
3
votes
0
answers
189
views
Time Complexity of Simulating CA with TM
This question is a follow up to the question: Proving Equivalence of 1-dimensional Cellular Automaton and Turing Machines.
To simulate a CA with a TM, I used a construction which placed a marker on ...
- 232
2
votes
1
answer
922
views
Proving Equivalence of 1-dimensional Cellular Automaton and Turing Machines
I'm considering an automaton $A$ over a alphabet $\Sigma$, with a set of states $Q$, such that $\Sigma \subset Q$, which includes special "accept" and "blank" states not in $\Sigma$. It also has an ...
- 232