Timeline for Grammar and Real-numbers
Current License: CC BY-SA 4.0
15 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Oct 29, 2019 at 23:17 | comment | added | J D | The core of the CPU is the ALU: arithmetic/logic unit. Computer scientists are applied mathematicians/logicians, plain and simple. | |
| Oct 29, 2019 at 23:17 | comment | added | J D | You miss the point. If one grammar is rooted in an alphabet by which a character maps to an infinite language, then it is wrong to say that the whole system is finitely described. Those who created and defined the theory of computation were mathematicians and logicians. Turing, Church, Goedel, the list goes on. There's no crisp distinction between mathematics, logic, and computer science like you presuppose. The very nature of the decidability of computation is by nature a question strongly tied to the infinite: recursion, iteration, decidability, halting, formal languages. | |
| Oct 29, 2019 at 22:54 | comment | added | babou | @JD I do not state anywhere "that alphabets can be infinite". Of course, mathematicians can often introduce what they will, but it is then questionable whether it is still computation theory, whether it can be implemented. Your example does not prove anything, because, as you prove by your own description, the whole system is finitely described. | |
| Oct 29, 2019 at 22:40 | comment | added | J D | Not only can it be done, it is done within numerical and computer algebraic systems. The lines of semantics and syntax blur when coupling multiple grammars. | |
| Oct 29, 2019 at 22:39 | comment | added | J D | If user111345 is building a computer algebra system to deal with reals, then like arbitrary precision numbers, a finte alphabet with the terminal symbol R (reals) may be mapped onto another grammar with a second finite alphabet that has a grammar that itself is infinite. In this way, it is possible to use potentially infinite alphabets while never implementing an actually infinite alphabet. | |
| Oct 29, 2019 at 22:35 | comment | added | J D | You said "a general rule that formal devices used to define languages and computation in general are finitely defined". You've already conceded that alphabets can be infinite. From the WP article " An alphabet may contain an infinite number of elements;[3] however, most definitions in formal language theory specify alphabets with a finite number of elements, and most results apply only to them.". | |
| Oct 29, 2019 at 22:28 | comment | added | babou | @JD You seem to confuse syntax and semantics. The finiteness I refer to is the syntactic finiteness of the description of grammars, automata, and other computational devices. This description might sometimes denote infinite entities semantically, but the computation is always performed on syntactic representation. Ignoring ω automata and languages, all you ever deal with is finite. You start with finite input and finite devices, and you perform only finite computation step, so that after a finite time you still have only finite structures.No limitation in size, but nothing becomes infinite. | |
| Oct 29, 2019 at 21:11 | comment | added | rici | @J.D.: infinite and unlimited mean different things. Automata (as normally defined, not $\omega$ automata) are not capable of infinite computations. There is no limit to the number of steps, but every process which terminates do so after some finite number of steps. | |
| Oct 29, 2019 at 20:50 | comment | added | J D | @babou, in formal languages and automata, the infinite is on equal footing with the finite. In regex, for example, we use the symbols, * and + to represent the intervals [0,infinity] and [1,infinity], resp. In fact all grammars and automata (they are isomorphic) are capable of infinite processes. Not only do automata admit working with infinite sequences, but also non-deterministic ones too. In fact, in the study of class equivalences of models of computation, one can also field not just the infinite, but the seminfinite. en.wikipedia.org/wiki/Automata_theory | |
| Oct 29, 2019 at 20:25 | answer | added | J D | timeline score: 1 | |
| Oct 29, 2019 at 18:44 | comment | added | babou | Welcome to SE computer Science. There are probably exceptions for some abstract developments, but you should consider as a general rule that formal devices used to define languages and computation in general are finitely defined. Hence they do not use infinite sets such as the real numbers, or even the integer numbers. What is it that you want to define? What do you want to define it from? | |
| Oct 29, 2019 at 18:36 | history | edited | babou | CC BY-SA 4.0 |
attempt to clarify
|
| Oct 29, 2019 at 16:35 | answer | added | Daniel | timeline score: 3 | |
| Oct 29, 2019 at 16:25 | review | First posts | |||
| Oct 29, 2019 at 16:41 | |||||
| Oct 29, 2019 at 16:23 | history | asked | user111345 | CC BY-SA 4.0 |