Solving the Two-Dimensional Turing Machine Problem

AI Thread Summary
The discussion centers on proving that the languages accepted by two-dimensional Turing machines (2D TMs) are equivalent to those accepted by standard one-dimensional Turing machines (1D TMs). A participant suggests that injective mappings might be relevant to the proof and considers the possibility of mapping the 2D tape to a 1D tape. They express uncertainty about how to proceed with this approach. The conversation highlights the challenge of demonstrating this equivalence and the need for a clear method to establish the relationship between the two types of machines. Ultimately, the focus remains on finding a valid proof for the equivalence of language acceptance between 2D and 1D TMs.
Tony11235
Messages
254
Reaction score
0

Homework Statement



A two-dimensional Turing machine has the usual finite-state control but a tape that is a two-dimensional grid of cells, infinite in all directions. The input is placed on one row of the grid, with the head at the left end of the input and the control in the start state, as usual. Acceptance is by entering a final state, also as usual. Prove that the languages accepted by two-dimensional Turing machines are the same as those accepted by ordinary TM's.

Homework Equations


None.

The Attempt at a Solution



The problem COULD have something to do with injective mappings, but how use this to show the above...I am stuck.
 
Last edited:
Physics news on Phys.org
Would it make sense to map the two-dimensional tape into a one dimensional tape, afterwhich, the result follows?
 
Thread 'Have I solved this structural engineering equation correctly?'

Thread 'Have I solved this structural engineering equation correctly?'

Hi all, I have a structural engineering book from 1979. I am trying to follow it as best as I can. I have come to a formula that calculates the rotations in radians at the rigid joint that requires an iterative procedure. This equation comes in the form of: $$ x_i = \frac {Q_ih_i + Q_{i+1}h_{i+1}}{4K} + \frac {C}{K}x_{i-1} + \frac {C}{K}x_{i+1} $$ Where: ## Q ## is the horizontal storey shear ## h ## is the storey height ## K = (6G_i + C_i + C_{i+1}) ## ## G = \frac {I_g}{h} ## ## C...
View full post »

Similar threads

Design an Infinite NTM for Any Input String: Turing Machine Question
Replies
5
Views
2K
Comp Sci Problem on undecidable problems
Replies
6
Views
2K
Turing Machines & Undecidability
Replies
3
Views
3K
Is this a Turing-complete machine?
Replies
2
Views
2K
Is Alan Turing given too much credit when it comes to computers?
Replies
29
Views
5K
MHB Designing a Non-deterministic 2-Tape Turing Machine for a Specific Language
Replies
1
Views
2K
MHB Non-deterministic 2-tape Turing Machine
Replies
1
Views
1K
Halting Problem and Turing's Solution
Replies
9
Views
3K
MHB Solving Recursive Sets with Turing Machines
Replies
4
Views
3K
Turing machine problem to getting startet
Replies
1
Views
2K

Hot Threads

Recent Insights

Back
Top