Algorithm definition generalisation / time-entaglement phenomennon

In summary, the conversation discusses the general notion of algorithms as a model of computation with a finite number of steps. The concept of a Turing machine is introduced as the most general model for computations, and the role of time in this model is questioned. The possibility of changing the notion of time order in a Universal Turing Machine to a notion of abstract order is also mentioned, and the potential influence of time-entanglement on our computational models is considered. The conversation concludes with a request for answers to several questions posed by the speaker.
  • #1
kakaz
17
0
Please let me mention certain idea here, although it is very vague.

The general notion of algorithm is model of computation with finite number of steps which my be performed on device from "set of computational devices". Up to now "Set of Computational devices" consists of quantum and classical computers which both may be simulated on Universal Turing Machine. It means that Turing machine remains the most general model for computations ( which is in harmony with other notions of effective computable functions like lambda-calculus or recursive functions).

So let me explain motivation to as question at the end:

Turing Machine is in some way connected with notion of time (it is idealisation of computation by performing "one operation" at a time). As we discover new interesting phenomena ( famous discovery: http://arxiv.org/abs/1101.2565 mentioned also here http://www.technologyreview.com/blog/arxiv/26270/ ) probably it is time to ask what is the role of time in Turing Computation model and if it has rigorous enough definition.

Lets imagine simple Gedankenexperiment: Imagine class of TM for which initial Data and Result has to be at least 4 ( in general n - natural number) cells one after other - it looks like artificial idea, but when we refer to separation in time - it sound very natural. We use "separation in time" as very natural notion: in fact we require it - answer has to be obtained after question - right?. So, in a light of existence of phenomenon like time-entanglement - mentioned in references above - it is probably time for review... It is not clear for me if this phenomenon point on something new but it may...

Of course "notion of time" may be not important here at all: maybe notion of order is sufficient enough ( although I do not know how such change would result in quantum computations where time is important parameter I suppose, but we may say - in mathematical idelisation/model probably it may be not important).

(1) Is it new idea or it is old?

(2) Is it interesting?

(3) If ten we change notion of time order in UTM to notion of abstract order, will that change notion of algorithm/Turing Machine definition?

(4) Is there any influence of time-entitlement on our computational model discussed?
 
Last edited by a moderator:
Technology news on Phys.org
  • #2
(5) Is there any influence of time-entitlement on our computational model discussed? I hope that ideas above may motivate you to answer - so I am looking forward for your answers.
 

1. What is an algorithm?

An algorithm is a series of specific steps or instructions designed to solve a problem or perform a task. It is often used in computer programming and can be thought of as a recipe for solving a problem.

2. How does an algorithm work?

An algorithm works by breaking down a complex problem into smaller, more manageable steps. These steps are then followed in a specific order to reach the desired outcome or solution.

3. What is generalisation in relation to algorithm definition?

In algorithm definition, generalisation refers to the ability of an algorithm to solve a wide range of similar problems, rather than being limited to a specific instance or situation. It involves identifying common patterns and creating a more general solution that can be applied to various scenarios.

4. What is the time-entanglement phenomenon in algorithms?

The time-entanglement phenomenon in algorithms refers to the concept that the time it takes for an algorithm to run can be affected by the initial state or starting point of the algorithm. This means that even small changes in the input data can significantly impact the amount of time it takes for an algorithm to complete.

5. How can the time-entanglement phenomenon be addressed?

To address the time-entanglement phenomenon, algorithms can be optimized and improved by reducing the number of steps or instructions, using more efficient data structures, or implementing parallel processing techniques. Additionally, careful consideration of the input data and its potential variations can help mitigate the impact of time-entanglement on algorithm performance.

Similar threads

  • Programming and Computer Science
Replies
29
Views
2K
  • Programming and Computer Science
Replies
2
Views
718
  • Programming and Computer Science
Replies
7
Views
1K
  • High Energy, Nuclear, Particle Physics
Replies
1
Views
1K
  • High Energy, Nuclear, Particle Physics
Replies
9
Views
1K
Replies
12
Views
687
  • Set Theory, Logic, Probability, Statistics
Replies
2
Views
985
  • Quantum Interpretations and Foundations
Replies
2
Views
648
  • Quantum Interpretations and Foundations
Replies
5
Views
807
Back
Top