Recent Entries 4
- pattern minor 112d agoIs the Turing machine the only framework to analyse limits of computation?In Theory of Computation lessons, the limits of computation are usually analyzed within the framework of Turing machines, so if something isn't solvable with Turing Machine, then we consider this problem as undecidable. I know computational models like Lambda Calculus are equivalent due to Turing-completeness, but why do we only consider the Turing machine as a model of general-purpose computation? For example, in Physics, the Newtonian Framework has its own theory about light and about interaction time speed, but that framework fundamentally changed in 20th century which gave us new capabilities(or restrictions) theoretically. Is such a fundamental change viable in computer science, or we do consider Turing and early 20th century foundations similarly as quantum physics is to realm of physics. Why do we work within the framework and don't try to change fundamentals such that things that may be undecidable become decidable within another framework?
- pattern moderate 112d agoWhat are the conditions necessary for a programming language to have no undefined behavior?For context, yesterday I posted Does the first incompleteness theorem imply that any Turing complete programming language must have undefined behavior?. Part of what prompted me to ask that question in the first place is that, awhile ago, someone on the learnprogramming subreddit told me something about the reason C++ in particular having so much undefined behavior is because, for it to not have undefined behavior, it would have to use a much more restrictive language model, but they didn't explain what that means exactly. I had also asked on Quora awhile ago about why C++ compilers don't always throw errors when a program contains undefined behavior and at least one answer mentioned something about it being fundamentally impossible to always detect undefined behavior at compile time and that this was related to the halting problem being undecidable. Those two things combined have me wondering about models of computing more generally -- my understanding is that all/most popular programming languages, including C++, are Turing complete, and since I was told the problem of detecting UB in C++ is fundamental and related to the halting problem, I thought that perhaps all Turing complete programming languages must have undefined behavior and C++ is just worse at hiding it than others. But judging from the answers to my above-linked question, I was mistaken about that. So my question now is, what conditions need to be imposed on a Turing complete language in order to guarantee that all possible programs written in the language will have fully defined behavior determined by the language specification? And, on a side note, does the answer have anything to do with the incompleteness theorems? I ask the latter question because the idea of defining a language for which all possible programs have fully defined behavior seems quite similar to the idea of defining an axiom system for which all possible theorems are provable/disprovable.
- principle minor 112d agoEffectively decidable vs. noneffectively (or ineffectively) decidableThe introduction of https://www.sciencedirect.com/science/article/pii/0001870882900482 starts with the following sentence: The word problem for commutative semigroups is effectively decidable. I know what a “decidable” problem or, more precisely, a “decidable” language over an alphabet means: there is an algorithm that terminates on every input and returns “yes” or “no”, depending on whether the input belongs to the language or not. So, if the sentence were “The word problem for commutative semigroups is decidable”, I'd think this: for each (most likely, finite) alphabet $$ and each commutative semigroup $\langle G,\mathord\circ\rangle$, where $G\subseteq ^*$, there is an algorithm that, started with a string $s\in ^*$ as input, terminates and says whether $s\in G$ or not. Please correct me if I'm wrong. Now, what the hell does effectively mean? Is there anything non-effectively decidable or ineffectively decidable? How would effectively decidable be different from ineffectively decidable or non-effectively decidable?
- pattern minor 112d agoA language is Turing recognizable iff it is a projection of a decidable languageI was wondering how to prove that a language $C$ is Turing-recognizable iff a decidable language $D$ exists such that $C = \{x \mid \exists y \;(\langle x, y\rangle \in D)\}$. I do not know how to prove this kind of questions, is there any help to solve this problem or any problem as this kind?