# Questions tagged [theory]

The tag has no usage guidance.

57 questions
Filter by
Sorted by
Tagged with
2k views

### What is so fundamental about polynomial functions that they are used to demarcate the Hardness boundary in NP complexity classes?

This question has been bugging me ever since I first came across the concept of NP, NP-Complete, and NP-Hard a few years back: what is so fundamental about the polynomial functions that they are used ...
• 251
1 vote
168 views

### Two Generals' Problem - Thought Experiment

After reading the Two Generals' Problem, I am wondering as to why there isn't any solution and please correct me if I am missing something. What if, the generals decide that they will attack if they ...
23 views

### Are there any example of practical application of counter machines?

I am currently working on a presentation over how counter machines are as effective as Turing machines. During my research, I found out that random access machines are an improved version of counter ...
64 views

### Theoretical origin of acquire semantics only for reads?

What theoretical concept lies behind the strong restriction of acquire semantics - to reads, and release semantics - to writes? (With papers titles and authors, if possible.) Is it related to ...
• 151
118 views

### For an NFA with langauge: {w ∈ {0, 1}*: the length of w is odd but not a multiple of three}. How many states are required?

For an NFA with language: {w ∈ {0, 1}*: the length of w is odd but not a multiple of three}. How many states are required? This is the work I have come up with so far: q0: non-accepting state - ...
43 views

### Prove that if $L \subseteq b^*$ isn't regular then $M = a^+L \cup b^*$ isn't regular

There is an exercise in a book about finite automata that I couldn't solve: Prove that if $L \subseteq b^*$ isn't regular then $M = a^+L \cup b^*$ isn't regular either, using the fact that REG is ...
• 1,467
59 views

### Turing Machine Decidability [closed]

Consider the language $L = \{\langle M_1,\ M_2 \rangle \mid \exists x : x \in L(M_1) \cap L(M_2)\}$. Show that $L$ is not decidable. I'm attempting a proof by contradiction but I'm having trouble with ...
224 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 ...
• 83
84 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 ...
• 149
1 vote
38 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?
230 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 ...
371 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 (...
• 43
4k views

• 123
6k 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!
• 29
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
1 vote
693 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 ...
50 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 ...
• 103
271 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 ...
• 99
49 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 ...
1k 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,142
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 ...
• 11
1 vote
106 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, ...
313 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 ...
64 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
63 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 ...
114 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 ...
48 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 ...
• 155
1 vote
86 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, ...
• 155
348 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 ...
• 1
39 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 ...
• 1
390 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 ...
92 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 ...
• 13
1 vote
70 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 ...
• 11
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 ...