N-dimensional Universal Turing Machine?

Click For Summary

Discussion Overview

The discussion revolves around the capabilities of a Universal Turing Machine in computing sequences of integers in N-dimensional spaces. Participants explore the implications of dimensionality, the nature of sequences, and the computational requirements involved.

Discussion Character

  • Exploratory
  • Technical explanation
  • Conceptual clarification
  • Debate/contested

Main Points Raised

  • One participant questions whether a Universal Turing Machine can compute arbitrary, orthogonal sequences of integers in N dimensions for any N>0.
  • Another participant seeks clarification on the term "orthogonal," suggesting it may refer to N-dimensional vectors with integer entries.
  • A participant proposes a model likening the computation to a crossword puzzle with cells containing integers, where Turing tapes run perpendicular to each other.
  • There is a suggestion that if each cell has a non-negative integer index sequence, it may be possible to compute the sequences, assuming N is not too large for computational feasibility.
  • A later post redefines the question to focus on the minimum number of Universal Turing Machines needed to compute all distinct sequences of integers in an infinite N-dimensional space, questioning whether the answer is derived from set theory.
  • Another participant introduces the halting problem as a relevant consideration and questions the size of the set of sequences, emphasizing the importance of defining constraints and upper bounds.
  • Concerns are raised about the practical implications of using an infinite theoretical tape, with an example given regarding the computation of pi to illustrate potential limitations.

Areas of Agreement / Disagreement

Participants express varying interpretations of the original question and propose different models for understanding the computation of sequences. There is no consensus on the feasibility or the specific requirements for computing these sequences in N dimensions.

Contextual Notes

Participants highlight the need for clear definitions and constraints regarding the sequences and dimensions involved, as well as the implications of the halting problem on practical computation.

Who May Find This Useful

Individuals interested in theoretical computer science, particularly in the context of Turing machines, dimensional computation, and the implications of the halting problem.

Loren Booda
Messages
3,115
Reaction score
4
Can a Universal Turing Machine compute arbitrary, orthogonal sequences of integers in N dimensions for any N>0?

Just an idea.
 
Physics news on Phys.org
Hey Loren Booda.

What do you mean by orthogonal exactly? Do you mean an N-dimensional vector where each entry is an integer?
 
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.
 
Loren Booda said:
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.
 
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?
 
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.
 
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
 

Similar threads

MHB Can Turing Machine Decidability Extend to Complex Algorithm Outputs?
  • · Replies 1 ·
Replies
1
Views
2K
MHB Designing a Non-deterministic 2-Tape Turing Machine for a Specific Language
  • · Replies 1 ·
Replies
1
Views
2K
Undergrad Would Infinite Time Resolve the Halting Problem?
  • · Replies 9 ·
Replies
9
Views
2K
Undergrad Can Turing Machines Understand Infinity?
  • · Replies 14 ·
Replies
14
Views
2K
Graduate Computability in Classical Physics
  • · Replies 2 ·
Replies
2
Views
2K
Is Alan Turing given too much credit when it comes to computers?
  • · Replies 29 ·
Replies
29
Views
6K
Graduate Questions concerning the Church-Turing thesis
  • · Replies 3 ·
Replies
3
Views
2K
Undergrad Turing machine problem to getting startet
  • · Replies 1 ·
Replies
1
Views
2K
Have a Turing Machine? Can it solve linear algebraic equations?
  • · Replies 2 ·
Replies
2
Views
2K
Graduate What is the slowdown of a universal circuit compared to a Turing machine?
  • · Replies 1 ·
Replies
1
Views
2K