Solving the Two-Dimensional Turing Machine Problem

Click For Summary
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). The key approach involves utilizing injective mappings to transform the two-dimensional tape into a one-dimensional representation. This transformation allows for the application of existing proofs regarding 1D TMs, thereby establishing the equivalence of the two machine types in terms of language acceptance.

PREREQUISITES
  • Understanding of Turing machine theory
  • Familiarity with finite-state control mechanisms
  • Knowledge of injective mappings and their properties
  • Concept of language acceptance in computational theory
NEXT STEPS
  • Research the concept of injective mappings in depth
  • Study the formal definitions and properties of Turing machines
  • Explore proofs of language equivalence between different computational models
  • Investigate the implications of two-dimensional computational models in theoretical computer science
USEFUL FOR

The discussion is beneficial for computer science students, theoretical computer scientists, and researchers interested in computational models and their language acceptance properties.

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?
 

Similar threads

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