patternMinor
Is there any other computation theory besides the one in automata theory?
Viewed 0 times
besidesthecomputationtheoryanyautomataotheronethere
Problem
I'm a bit confused at a fundamental level.
In Computer Science, maybe some of us mostly use discrete mathematics since our computer is digital (like during studying operating system, algorithms, security, or automata theory for example). Of course, there are also calculus and nonlinear mathematics in Computer Science, but it seems to me that that doesn't matter in the subject Theory of Computation.
Theory of Computation is supposedly for machines. In Theory of Computation, the object of interest is languages and one-dimensional strings/sequences of symbols.
But why is it that it's only for linear, one-dimensional sequences of symbols? The natural phenomenon is also more to analog than digital (take a look at physics, waves for example). Does it mean that Theory of Computation or Theory of Automata is restricted only to machines/computation that is using one-dimensional strings/sequences of symbols?
In general, not only in Computer Science, is there any other object of interest for computation, other than languages and strings? Since languages and strings of symbols are discrete. What about nonlinear mathematics, dynamical system, and wave for example? They are not strings of symbols, right? So, what about their Computation Theory? Is it still restricted to automata, grammars, Turing machine, or are they totally something different?
Are all things can be represented with languages/ strings of symbols? Are languages/string of symbols enough to represent any thing/phenomenon?
What is computation theory exactly for things other than languages/ strings of symbols (if any)?
Sorry that I don't know how to phrase all these better. Can somebody please enlighten me, or provide any keywords that I can search for? Thank you very much!
In Computer Science, maybe some of us mostly use discrete mathematics since our computer is digital (like during studying operating system, algorithms, security, or automata theory for example). Of course, there are also calculus and nonlinear mathematics in Computer Science, but it seems to me that that doesn't matter in the subject Theory of Computation.
Theory of Computation is supposedly for machines. In Theory of Computation, the object of interest is languages and one-dimensional strings/sequences of symbols.
But why is it that it's only for linear, one-dimensional sequences of symbols? The natural phenomenon is also more to analog than digital (take a look at physics, waves for example). Does it mean that Theory of Computation or Theory of Automata is restricted only to machines/computation that is using one-dimensional strings/sequences of symbols?
In general, not only in Computer Science, is there any other object of interest for computation, other than languages and strings? Since languages and strings of symbols are discrete. What about nonlinear mathematics, dynamical system, and wave for example? They are not strings of symbols, right? So, what about their Computation Theory? Is it still restricted to automata, grammars, Turing machine, or are they totally something different?
Are all things can be represented with languages/ strings of symbols? Are languages/string of symbols enough to represent any thing/phenomenon?
What is computation theory exactly for things other than languages/ strings of symbols (if any)?
Sorry that I don't know how to phrase all these better. Can somebody please enlighten me, or provide any keywords that I can search for? Thank you very much!
Solution
There is indeed computability-theory for non-discrete settings. This area is called computable analysis. A decent tutorial to computable analysis is here (if you have an institutional subscription, or can get it from a library):
https://link.springer.com/chapter/10.1007%2F978-0-387-68546-5_18
The tutorial focuses quite a bit on the case where we are computing with real numbers, or at least elements of metric spaces. Computable analysis can handle much more situations though. Roughly speaking, we probably have reasonable computability-notions for any kind of space appearing in ordinary mathematics.
It turns out that many concepts from the classical, discrete computability theory still apply, but topological aspects also become very relevant.
https://link.springer.com/chapter/10.1007%2F978-0-387-68546-5_18
The tutorial focuses quite a bit on the case where we are computing with real numbers, or at least elements of metric spaces. Computable analysis can handle much more situations though. Roughly speaking, we probably have reasonable computability-notions for any kind of space appearing in ordinary mathematics.
It turns out that many concepts from the classical, discrete computability theory still apply, but topological aspects also become very relevant.
Context
StackExchange Computer Science Q#100644, answer score: 3
Revisions (0)
No revisions yet.