Equivalence of models with respect to Turing-recognizability and -decidability

In summary, the conversation discusses the concept of equivalence between computational models and the problem of decidability when dealing with models that can run indefinitely. It also brings up the question of whether two models decide the same languages if and only if they recognize the same languages. The conversation also raises the issue of defining a "model of computation" and the possibility that a model may not necessarily "decide" in the traditional sense.
  • #1
alexfloo
192
0
This seemed like the least inappropriate place for this. Feel free to move it if I am wrong.

Generally speaking, two computational models are equivalent if they recognize the same class of languages. In the case of models that can run indefinitely, we also have the problem of decidability. Generally, we make no mention of decidability in equivalence proofs.

I understand that a Turing-recognizable language is decidable if and only if its complement is Turing-recognizable. Can this fact be used to prove that a model decides the decidable languages if and only if it recognizes the Turing-recognizable languages?

Can it be shown more generally two models decide the same languages if and only if they recognize the same languages?

Clearly this problem isn't completely specified, since to my knowledge a "model of computation" is as loosely defined today as an "algorithm" was pre-Turing. (By the way is there any theory about something resembling a "category of computational models?")
 
Physics news on Phys.org
  • #2
Hey alexfloo.

In terms of the language, does one language have to be the same or can it be a subset of the other language?
 
  • #3
I actually managed to find a partial answer, which is that even my first question was ill-formed.

The enumerator is equivalent to the TM in that they recognize the same languages, but enumerators decide exactly the finite languages. For any infinite language, an enumerator enumerates infinitely.

Furthermore, it raises the point that a model (at least until we have a better definition of it) need not "decide" at all.

For instance, we have the trivial model "the set" which accepts if it contains a string and rejects otherwise. It recognizes the class of all languages, unrestricted. It may make sense to say that it decides the same languages it accepts, but it illuminates that a model may not have a parallel as a "process" which can "run infinitely" or "not run infinitely," and decidability need not make sense with respect to any model
 

Related to Equivalence of models with respect to Turing-recognizability and -decidability

1. What does "equivalence of models" mean in the context of Turing-recognizability and -decidability?

The equivalence of models refers to the idea that different models of computation, such as Turing machines or cellular automata, can be used to solve the same computational problems. This means that if a problem is Turing-recognizable or -decidable in one model, it can also be solved in another model.

2. How do we determine if two models are equivalent in terms of Turing-recognizability and -decidability?

We can determine if two models are equivalent by showing that one model can simulate the other. This means that for any instance of a problem, the first model can produce the same output as the second model. If this is true, then the models are considered equivalent in terms of Turing-recognizability and -decidability.

3. Can two models be equivalent in one aspect but not in the other (e.g. Turing-recognizability but not -decidability)?

Yes, it is possible for two models to be equivalent in terms of Turing-recognizability but not in terms of -decidability. This means that one model can recognize the language of another model, but it may not be able to decide all problems that the other model can decide.

4. How does the equivalence of models impact the study of computability?

The equivalence of models is an important concept in the study of computability because it allows us to compare the power of different models of computation. It also helps us understand the limitations of certain models and how they relate to each other in terms of solving computational problems.

5. Are all models equivalent in terms of Turing-recognizability and -decidability?

No, not all models are equivalent in terms of Turing-recognizability and -decidability. Some models, such as the lambda calculus, have a different set of rules and capabilities than Turing machines. However, many models have been shown to be equivalent to Turing machines, including lambda calculus, which means that they have the same level of computational power.

Similar threads

MHB Can Turing Machine Decidability Extend to Complex Algorithm Outputs?
    • Set Theory, Logic, Probability, Statistics
Replies
1
Views
2K
Turing-recognizable infinite language, decidable subset
    • Engineering and Comp Sci Homework Help
Replies
3
Views
2K
I Linear Model with independent categorical variable
    • Set Theory, Logic, Probability, Statistics
Replies
5
Views
1K
Is Alan Turing given too much credit when it comes to computers?
    • Programming and Computer Science
Replies
29
Views
3K
I Computer languages as examples in formal logic
    • Set Theory, Logic, Probability, Statistics
2
Replies
40
Views
7K
Comp Sci Problem on undecidable problems
    • Engineering and Comp Sci Homework Help
Replies
6
Views
2K
Halting Problem and Turing's Solution
    • Computing and Technology
Replies
9
Views
2K
I Recursive Ordinals and Creativity
    • Set Theory, Logic, Probability, Statistics
Replies
4
Views
1K
Understanding busy beavers (noncomputability)
    • Programming and Computer Science
Replies
2
Views
859
MHB The Causal Revolution and Why You Should Study It
    • Set Theory, Logic, Probability, Statistics
Replies
1
Views
1K

Hot Threads

Recent Insights

Back
Top