Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

N-dimensional Universal Turing Machine?

  1. Dec 26, 2011 #1
    Can a Universal Turing Machine compute arbitrary, orthogonal sequences of integers in N dimensions for any N>0?

    Just an idea.
  2. jcsd
  3. Dec 27, 2011 #2


    User Avatar
    Science Advisor

    Hey Loren Booda.

    What do you mean by orthogonal exactly? Do you mean an N-dimensional vector where each entry is an integer?
  4. Dec 27, 2011 #3

    More like a crossword puzzle with arbitrary number of squares and dimension, where each cell has an integer associated with it, and Turing "tapes" run perpendicular to each other.
  5. Dec 27, 2011 #4
    Do you mean each cell has a non negative integer index sequence i,j,k,.......,n ? If this is sufficient, I don't see why this wouldn't be possible provided n isn't too large to be accommodated computationally.
  6. Dec 27, 2011 #5
    Please allow me to redefine my question:

    A Universal Turing Machine computes, with minimal operations, all sequences of integers along an infinite (conventionally "one-dimensional" and partitioned) tape.

    What is the least number of such machines needed to compute all distinct sequences of integers occurring in an infinite N-dimensional space of random integers, where N is a whole number?

    Is the answer from simple set theory, or is it even more obvious?
  7. Dec 28, 2011 #6


    User Avatar
    Science Advisor

    The idea of the infinite theoretical tape won't really help you to give a practical solution.

    One thing that might help you is to consider the halting problem. Gregory Chaitin who worked for IBM has written a lot about the halting problem and has also found a way to express the probability of a turing machine halting given that the program is n-cells in length.

    Also with the sequences part of the question, what is the size of the set? I'm assuming by sequences you mean { a(n) } a(n) is an integer for all appropriate n where n ranges from 1 to some upper bound. What kind of upper bound do you have in mind?

    Putting the length of the actual "used" part of the tape into the context of the problem is important.

    Maybe it might be beneficial for everyone to know the exact constraints you have in mind.

    As an example if a computer were asked to compute the exact value of pi using integers and arithmetic, it could never be done in any finite amount of time and I worry that there may be some confusion that is in a similar vein.
  8. Dec 31, 2011 #7

    Thanks for giving grist to my mill for the upcoming year.

    (I received the book The Annotated Turing, by Charles Petzold, during the Holidays.)

Share this great discussion with others via Reddit, Google+, Twitter, or Facebook