5
$\begingroup$

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!

Improve this question
$\endgroup$
3
  • 2
    $\begingroup$ Not all computers are digital: en.wikipedia.org/wiki/Analog_computer ...That being said, theoretical CS is (mostly?) discrete because most of it grew out of semi-Thue systems, which are essentially symbol-rewriting systems. $\endgroup$
    – dkaeae
    Commented Nov 28, 2018 at 9:55
  • $\begingroup$ Thank you for the information. Symbol-rewriting system.. analog computer.. So it means that actually there's much more to computation than symbol-rewriting systems/ languages/ strings, right? $\endgroup$
    – kate
    Commented Nov 28, 2018 at 11:11
  • 1
    $\begingroup$ The discrete domain is not restructed to strings only. There are automata and grammars for trees, graphs and grids. $\endgroup$
    – Hendrik Jan
    Commented Nov 28, 2018 at 16:07

3 Answers 3

Reset to default
3
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Thank you for introducing this. From what I read, it also relates to/ use Turing Machine. So is this also can be seen as an extended version of Theory of Automata as well? $\endgroup$
    – kate
    Commented Sep 21, 2020 at 13:38
  • 1
    $\begingroup$ @kate Indeed, computable analysis can be seen an extension of the traditional computability theory, and computability on discrete structures naturally arises as a special case in computable analysis. $\endgroup$
    – Arno
    Commented Sep 21, 2020 at 13:55
2
$\begingroup$

Your question is very philosophical in nature because you are asking about what is considered by computation and it’s physical implementations. In short, there is a ongoing discussion on different accounts of concrete computation e.g. the simple mapping account, the semantic account, the syntactic account, the mechanistic account, the causal, the counterfactual and the dispositional account.

This stanford plato article will help you understand each and their implications. https://plato.stanford.edu/entries/computation-physicalsystems/

Improve this answer
$\endgroup$
3
  • $\begingroup$ We're not looking for link-only answers. Those answers become useless if the link stops working. Also, we don't want to be just a link farm; we want to generate useful new content ourselves. Please edit your answer to summarize the main ideas in a self-contained way that will remain useful even if the link stops working. Thank you! $\endgroup$
    – D.W. ♦
    Commented Dec 4, 2019 at 19:15
  • $\begingroup$ Right sorry, I’ll edit my answer $\endgroup$
    – Yos
    Commented Dec 4, 2019 at 19:21
  • $\begingroup$ Yos, i know it's late for me to reply, but this is such an interesting read! Thank you so much for introducing this. $\endgroup$
    – kate
    Commented Sep 21, 2020 at 13:29
1
$\begingroup$

Computer science is not entirely contained in symbolic logic, but it is impossible for a computational model to be 100% continuous: to be a model is to be representational, is to be symbolic, in some sense.

That concern is at the heart of where computer science comes from, historically. It is not a field devoted to the "computational understanding of reality", even thought this may an interesting peripheral issue to many of us. It is not primarily the study of concrete computational systems, even thought they are our visible face to society. It is, originally, the study of how mathematics can formally reason about itself. Concrete computational systems are of interest to us, as much as they can "reason" about themselves, representationally. That's what software is.

Our current, common sense understanding of symbol is rooted in the connection between digital and textual. Strings of characters is what we got. That may change someday.

Improve this answer
$\endgroup$
2
  • $\begingroup$ This is insightful, thank you so much. So, concrete computational system = software; does this "concrete computational system" also refers to Turing machine/automata? $\endgroup$
    – kate
    Commented Sep 21, 2020 at 13:33
  • $\begingroup$ By "concrete computational system" I'm referring to what is empirically observable that can be used to perform a computation. The sun helps us compute the duration of a day, for instance. $\endgroup$
    – André Souza Lemos
    Commented Sep 21, 2020 at 17:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.