N-dimensional Universal Turing Machine?

[Loren Booda]

Can a Universal Turing Machine compute arbitrary, orthogonal sequences of integers in N dimensions for any N>0?

Just an idea.

 

[chiro]

Hey Loren Booda.

What do you mean by orthogonal exactly? Do you mean an N-dimensional vector where each entry is an integer?

 

[Loren Booda]

chiro,

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.

 

[SW VandeCarr]

chiro,

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.

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.

 

[Loren Booda]

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?

 

[chiro]

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.

 

[Loren Booda]

chiro,

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

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

-Loren