# Questions tagged [theory]

The tag has no usage guidance.

57 questions
Filter by
Sorted by
Tagged with
32 views

### Turning machines

Consider the language L = {<M1 , M2> | Ǝx such that x ∈ L(M1) ∩ L(M2)} Show that L is not decidable. Im doing a proof by contradiction but im having trouble with the turning machine part
1 vote
26 views

### Is there any reference materials on complexity analysis for lazy languages?

Is there any books, papers or articles on how to analyze the time complexity of programs written in lazy languages such as Haskell? I know how laziness is implemented and how it can be expanded and ...
129 views

### How do I improve my problem-solving and creative thinking skills in Computer Science?

I am a CS undergrad trying to improve my problem-solving skills. I have noticed that I have a problem with theoretical computer science which I've been trying to fix largely unsuccessfully till now. I ...
32 views

### What are the applications of Belief Revision?

In my Computer Science graduation, I came across this concept of Belief Revision, which focus on knowledge representation and the possible operations that can be done with the facts that a "...
59 views

### Can negative edge weights in a graph be positive numbers?

I'm a little confused by the concept of a "negative" edge weight. All of the examples I have seen represent negative edge weights as negative numbers. Is it possible for an edge weight to ...
50 views

### Enumerating Turing Machine (a,b)*

What does it mean to make an enumerating Turing machine of (a,b)*, since it has so many possibilities as to what the string can be. Do I just pick some random string and enumerate it like aab?
1 vote
37 views

### Which non regular language meets the requirements for pumping lemma for regular languages?

I heard in my lecture that there are non regular languages which meet the requirements for the pumping lemma for regular languages but I never actually saw one. Does anybody have an example?
121 views

### Why Regular Grammar is Left/Right Linear?

From the definition I know that regular grammar should be Left/Right Linear (ie it should have variable on Left/Right side of each production rules) But, my question is why it is mandatory? Can't we ...
33 views

### turing machine to add each number with the one next to it

im trying to make a turing machine that adds a number with the one next to it on the right. and after, it replaces that number with the result of the addition. for example if input is 1012, 1+0=1 (...
400 views

### regex for {w ϵ {a,b}*: |w| mod 3 =0}

I think this is what the regular expression would be. (aaa U aab U aba U abb U baa U bab U bba U bbb)*
250 views

### Intuition for Sipser's proof of PDA to CFG

I understood Sipser's proof of CFG to PDA but I am having a hard time understanding his proof of conversion from PDA to CFG while demonstrating the equivalence between the two. He splits the proof (...
3k views

5k views

### Could Gödel’s incompleteness theorem be circumvented with a quine?

As you all probably know, Gödel’s incompleteness theorem states, that it will never be possible for mathematics to prove its own correctness. Mainly because that proof would be part of mathematics too,... 1k views

### Can we solve a "very" exponential recurrence?

Can we solve this recurrence relation : $T_n = \exp(T_{n-1})$ ? Thanks!
47 views

### Is this an example of a zero-knowledge proof?

I want to prove to a verifier that I know the passcode of a system. The system contains data/information of the verifier of which is only contained with this system. Since I know the passcode to the ...
1 vote
405 views

### If Interpreters are used to run code and are written in another language, won't interpreters need interpreters?

As I was going through my online lectures, it is stated that python is interpreted with Cpython, a software written in C. Similarly, they have Jython (written in Java) and PyPy (written in Python). My ...
37 views

### Same instances for different problems

According to the formal definition of an instance, it is a set of input data containing the values of the parameters of some problem (What is an instance of NP complete problem?). So, two problems may ...
260 views

### Must a partial halt decider be a pure function of its inputs?

Must a partial halt decider be a pure function of its inputs? A partial halt decider correctly decides the halt status of some of its inputs. I am trying to write C code that would be acceptable to ...
38 views

### Existence of infinite unique FSAs

It is reasonably simple to show that there are an infinite number of different finite state automata that can be constructed, but has it been proven if there is an infinite number of unique finite ...
847 views

### Can a non deterministic finite automaton go into infinite loop?

Here is the exact same question but on deterministic finite automaton. The case for deterministic finite automaton is simple. For each state only one transition is possible for each input symbol and ...
1 vote
60 views

### Could someone explain the algorithm from this paper? (Thank you) [closed]

Trying to get a fair understanding of our artificial immune systems. To do this I’ve been reviewing this paper, but the algorithm and mathematics is over my head, could someone explain the below to me ...
38 views

### What is the name of this data structure?

I am trying to solve a problem efficiently. The problem is to recurse over a set $\{0,1,\dots,n-1\}$ (as array) in ascending or descending order, while removing or re-adding items in $O(1)$ time. A ...
1 vote
77 views

### Should I be a good computer scientist to become a great software developer?

As I am headed into a Computer Science major wishing to eventually become a software developer, I wonder this: should I immerse myself in computer science theory and knowledge (data structures, ...
251 views

### Turing, RAM, or Von Neumann --- which theory/model is the consensus?

I am not a formal student for CS nor have I ever been, I just want to understand something simple about your field for general knowledge, in plea. Turing, RAM, or Von Neumann --- which theory/model is ...
54 views

### Is memorization necessary in learning computer science?

Backgrounds Hi guys, I am now trying to teach myself some basic computer science theories. Specifically, I am using the book, CSAPP (computer systems, from a programmer’s perspective) and 15-213 ...
72 views

### Is this language a context free language?

Consider the following language, where the alphabet is $\{0, 1, 2\}$: $B = \{0^a1^b2^c|a, b, c \geq 0 \text{ and }c = ab + 1\}$. Is this language a context free language? Prove your answer. I am ...
1 vote
53 views

### Artificial Intelligence: theory vs processing power

It is common to see articles praising the advances in AI (here is one example). There is no doubt that significant progress has occurred on all kinds of automation, hard games like chess, etc. The ...
113 views

### Is the base of natural logarithms $e$ efficiently computable?

Is $e = 1 + \frac{1}{1!} + \frac{1}{2!} + \frac{1}{3!} + \frac{1}{4!} +\ldots$ efficiently computable? To be more specific, we say that a real number $r$ is efficiently computable if there is a ...
44 views

### Is there a "theory" of operating systems?

Is there a theory for Operating Systems? That is, subfields of CS have theoretical parts; i.e. PL has type theory, ML has mathematical theorems, security has a lot of provable properties, etc. There ...
1 vote
85 views

### What's beautiful in CS? [closed]

I'm afraid this may be opinion-based and not apt here, but... Mathematicians often talk about "mathematical beauty", i.e. Gauss' proof of the Fundamental Theorem of Algebra, Euler's Formula, ...
271 views

### "If any problem in NP is not polynomial-time solvable, then no NP-complete problem is polynomial-time solvable."

This is given vertabim in my lecture slides and it seems like I'm having difficulty proving this statement mathematically. I know that P is a subset of NP and NP-Complete is also a subset of NP. But ...
38 views

### How to get a piece of the Pie? Theoretical Plate Stacking Problem

This is just a theoretical problem that I found in the wild and want to know your solution. A stack of plates is made between you a cousin and a few others. Every (4 to 7) many random hours the plate ...
382 views

### Forest characterization

Prove that each property below characterizes forests... a. every induced subgraph has a vertex of degree at most one. When proving a characterization, do we have to prove both directions, like an if ... 82 views

### string concatenation vs language concatenation

What exactly is the difference between $$C = \{a^*\}\{b\}\{a^*\}\{b\}\{a^*\}\{b\}$$ and $$D = \{a^nba^nba^nb | n \geq 0 \}$$ It is known that D is non-regular and C is regular, but I am not sure ...
1 vote
67 views

### Level Ancestor Query long-paths algorithm complexity of sqrt n

Can someone explain why the complexity of a query for LA is √n when we only decompose the tree into long-paths? How can we show/prove that? How can we prove that the number of paths can be as high as ...
54 views

### Consistent theory based on L and not(A->A) is a theorem

I am working on this problem in which I have a theory $T$ based on language $\mathcal{L}$ and the only information we have is that T is consistent and $\vdash \lnot(A \rightarrow A)$. Given this ...