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!

  • 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 Nov 28 '18 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 Nov 28 '18 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 Nov 28 '18 at 16:07

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):


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.


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/

  • $\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. Dec 4 '19 at 19:15
  • $\begingroup$ Right sorry, I’ll edit my answer $\endgroup$ – Yos Dec 4 '19 at 19:21

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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