All mathematical questions about computer science, including theoretical computer science, formal methods, verification, and artificial intelligence. For questions about Turing computability, please use the (computability) tag instead. For numerical analysis, use the (numerical-methods) tag. For ...

learn more… | top users | synonyms

3
votes
1answer
233 views

Is every recursively enumerable set $A \subseteq \mathbb{N}$ also recursive?

Is every recursively enumerable set $A \subseteq \mathbb{N}$ also recursive ? I'm not particularly interested in a detailed proof or counterexample, just a quick argument why this affirmation should ...
3
votes
1answer
337 views

If P/Poly does not contain NP then does SAT require super-polynomial circuits?

I have a basic question about circuit complexity. Apparently no example of a language that requires super-polynomial circuits to decide is known. (This is despite the fact that an easy counting ...
3
votes
2answers
1k views

How can I prove that this set is recursively enumerable?

Let $g _c (x)$ be the output of a program that is encoded by $c \in \mathbb{N}$ for the given input $x$. $g_c$ can obviously be undefined, in case the program encoded by $c$ doesn't halt. If we define ...
1
vote
1answer
65 views

Identities for relations of the form (a,b). If it holds, how do you “prove” it?

First some context (binary relations) $F \subseteq W \times X \quad G \subseteq X \times Y \quad H \subseteq Y \times Z $ Does the following equality hold $(G \circ F)^{-1} = F^{-1} \circ G^{-1}$ ...
3
votes
3answers
198 views

Why can't we diagonalize out, if we deal with partial functions?

We know, that all (partial) recursive functions are countable (since one can for example interpret them as some simple programs; and the set of those programs are themselves countable), so one can try ...
3
votes
1answer
156 views

Uniform PRNG for long integer structures

Good morning! I don't actually know where to attribute this question (maybe it's better to publish it on StackOverflow), but it's more related to math theory than to actual realization. Since the ...
2
votes
2answers
212 views

A Function That Creates “Hello World!” [closed]

The classic string "Hello world!" can be translated to list of characters with ascii-codes: [72; 101; 108; 108; 111; 32; 87; 111; 114; 108; 100; 33] Is there a ...
3
votes
2answers
197 views

How do we know that there is a function from $\mathbb{N}$ to $\mathbb{N}$ that is not partial computable?

A partial computable function is also known as effectively computable, and is defined as any function that can be computed by a Turing machine with $Dom(f) \subseteq \Sigma^*$, where $\Sigma^*$ is the ...
0
votes
0answers
175 views

Terminology, mapping a tree to a tree

I have stumbled upon a problem; unfortunately, I do not know the proper terminology to be used which hinders me in thinking about the problem and explaining the problem. I am not even sure this is the ...
5
votes
1answer
241 views

What is the power of a recursive language vs. that of one that is recursively enumerable?

I am simply wondering, as the title states, what the central differences are between recursive and recursively enumerable languages? If I am not mistaken a recursive language is a is Turing decidable ...
2
votes
1answer
2k views

Probability of collision in binary exponential backoff

Four stations are trying to transmit frames through a single channel (only one frame per channel). After each frame is sent, they contend for the channel using Binary Exponential Backoff. After $i$...
9
votes
5answers
640 views

What is a good language to develop in for simple, yet customizable math programs?

I'm writing to ask for some guidance on choosing a language and course of action in learning programming. I've seen thread after thread with questions from newbies, asking, "What is the best language ...
0
votes
2answers
151 views

Formal language problem

I’m new to formal language and searching for the solution for the following task: $\Sigma$ is an alphabet with $\lvert \Sigma\rvert = 5$ and $k \in \mathbb{N}_0$. I’m searching for $\lvert \Sigma^k\...
0
votes
3answers
193 views

Formal language problem

Hello I´m new to formal language and searching the solution for the following task: Language: $L = \{0^{2i+1}|i\in\mathbb{N}_0\}$ Alphabet: $\Sigma = \{0\}$ I'm searching the resultion (sic) for: $\...
8
votes
4answers
14k views

What does it mean to say a language is context-free?

What does it mean to say a language is context-free?
3
votes
3answers
151 views

Diagonalizations and their relation to P and NP

I'm quoting the following (landmark) paper: Theodore Baker, John Gill, and Robert Solovay Relativizations of the P?=NP Question SIAM Journal of Computing, Volume 4, Number 4, December 1975, ...
1
vote
2answers
124 views

On TM's with a single loop

Thinking about the halting problem for TM's, I came up with a statement that I can't prove or disprove easily and would want your suggestions. Conjecture: Given a TM whose digraph has a single cycle ,...
6
votes
1answer
372 views

Rank of an interesting matrix

Lets define: $U=\left \{ u_j\right \} , 1 \leq j\leq N= 2^{L},$ the set of all different binary sequences of length $L$. $V=\left \{ v_i\right \} , 1 \leq i\leq M=\binom{L}{k}2^{k},$ the set of ...
9
votes
4answers
591 views

Consequences of solving the Halting problem

What impact would a device (ie super-computer or relativistic computer or other method) that solves the halting problem have on math? Would there be any mathematical problems left to solve? What ...
12
votes
4answers
1k views

What is undecidability

What does it mean that some problem is undecidable? For instance the halting problem. Does it mean that humans can never invent a new technique that always decides whether a turing machine will halt?...
1
vote
1answer
216 views

Does this number exist?

Consider the finite algorithm A, and the real number $0<T<1$. The output of A on input T is all possible theorems and provable propositions in ZFC, and only that. Q1. Can such an algorithm and ...
1
vote
3answers
206 views

Common algorithm with an order of Θ(2^n)

What would be a common algorithm with an order of Θ(2^n)? When I say "order", I mean time complexity analysis. I was thinking exponential growth but are there any that are more computer science ...
1
vote
3answers
173 views

Find the missing term

The sequence $10000, 121, 100, 31, 24, n, 20$ represents a number $x$ with respect to different bases. What is the missing number, $n$? This is from my elementary computer aptitude paper. Is there ...
0
votes
1answer
532 views

balanced 2-partition with equal cardinality (cardinality difference = 1 (max))

Given a set $S$ of $N$ numbers, my aim is to partition it into two sets ($S_1$ and $S_2$), so that (i) the difference $\sum S_1 - \sum S_2$ is minimized and (ii) the difference $|S_1| - |S_2|$ is $1$...
3
votes
2answers
387 views

How to solve recurrence relations with emphasis on algorithmic complexity

I am having trouble solving recurrence relations, probably because I am missing the basics. Is there any web reference/book I can read to help me cover the basics? I watched some lectures and read ...
10
votes
3answers
6k views

fast algorithm for solving system of linear equations

I have a system of linear equations, $Ax=b$, with $N$ equations and $N$ unknowns ($N$ large) If I am interested in the solution for only one of the unknowns, what are the best approaches? for ...
0
votes
1answer
303 views

Deriving an expression for an epipolar line

I would like to derive an expression for an Epipolar Line that appears in a right camera (there are two cameras - a left a right one). These cameras are placed in a $(x,y,z)$ vector space. This is a ...
2
votes
3answers
549 views

Regular Language Notation Language

What I would like to do is design a program (for academic purposes) which will take a representation of a DFA (as a directed graph) and display the regular language which it accepts, in a reasonable ...
16
votes
2answers
1k views

What is the complexity of succinct (binary) Nurikabe?

Nurikabe is a constraint-based grid-filling puzzle, loosely similar to Minesweeper/Nonograms; numbers are placed on a grid to be filled with on/off values for each cell, with each number indicating a ...
7
votes
2answers
2k views

Dijkstra's algorithm using heap

My teacher gave me a pseudocode of Dijkstra's algorithm using binary heap including the following steps (x was just extracted from the heap): For each vertex y such that it is a node for it in a ...
5
votes
2answers
922 views

Is this function a primitive recursive function?

Let $t \in \mathbb{N}$ and consider the function $f: \mathbb{N} \rightarrow \mathbb{N}$, defined by $f_t (m)= 2 \uparrow^{m} t$, where "$\uparrow$" is Knuth's up-arrow notation (which can be ...
0
votes
1answer
57 views

Probabilistic performance guarantees on information retrieval queries

The following is a question from lecture notes and although not assigned homework, I am trying to solve it. Assume that we have a collection $C$ of $N$ documents and a query $q$. There are $R_{q}$ ...
10
votes
1answer
763 views

Incremental calculation of inverse of a matrix

Does there exist a fast way to calculate the inverse of an $N \times N$ matrix, if we know the inverse of the $(N-1) \times (N-1)$ sub-matrix? For example, if $A$ is a $1000 \times 1000$ invertible ...
1
vote
1answer
217 views

Rank of a graph matrix

$G$ is a bipartite graph with $2m$ nodes on the left $(u_0..u_{2m-1})$, and $2^{m}$ nodes on the right $(v_0..v_{2^{m}-1})$. There is an edge (connection) between $u_i$ and $v_j$ iff $(i+1)$'th ...
5
votes
2answers
4k views

How to show that $ALL_{DFA}$ is in P

How can I show that $ALL_{DFA}$ is in P ? $ALL_{DFA} = \{ \langle A \rangle \mid A \text{ is a DFA and } L(A) = \Sigma^* \}$
2
votes
2answers
325 views

Recognizing language using Turing machine

Given integers $a, b, c$ construct a single-tape Turing machine recognizing the language $\{w \in \{0,1\}^{*}: a*\#_{0}w+b*\#_{1}w+c=0\}$ in time $O(n*logn)$, where $n=|w|$. $\#_{x}w$ denotes the ...
2
votes
1answer
335 views

Detecting cycles in off-line Turing machines

Let $M$ be an off-line Turing machine over the input alphabet $\{0,1\}^{*}$, that uses only one working tape in addition to the input tape. Construct a Turing machine $M'$, such that: $L(M) = L(...
6
votes
2answers
479 views

Faulty proof of polynomial hierarchy first level collapse?

I am an undergraduate of CS and I participate in TCS.SE. I am having trouble finding the error in a proof about the polynomial hierarchy collapsing to the first level ($NP = coNP$). I believe the ...
9
votes
3answers
745 views

NP vs NP-Complete

Is there any problem which is in NP but not in NP-Complete? Is there any possibility that this problem is analogous to P=NP problem, if so is there any problem which is in NP, but currently there is ...
2
votes
1answer
421 views

Proving problems are unsolvable - reducibility proof

Suppose we have P, a string denoting a C program which takes in a natural number as input and outputs at most one natural number. Prove that it is impossible (unsolvable) to determine that P has ...
2
votes
1answer
636 views

Considering math or computer science

Let me start by saying I graduated High School in 2002 and have worked as a technician, a systems administrator, and a part time web developer up till now. I have started taking courses at community ...
4
votes
1answer
2k views

How do you do a cross product of two $3 \times 3$ boolean matrices?

I have two boolean matrices: A = |1 1 0| |0 1 0| |0 0 1| and B = |1 0 0| |1 1 1| |0 0 1| What is the result of A x B and what are the steps ...
19
votes
2answers
24k views

Recognizable vs Decidable

What is difference between "recognizable" and "decidable" in context of Turing machines?
1
vote
2answers
592 views

Running 'Encrypted Code' on a Computer

Alice released a new version of her software for removing red-eye from pictures. However, she wants to protect her secret algorithm from disassemblers and such while still letting her customers remove ...
8
votes
1answer
362 views

is this language context free? [closed]

I need an NPDA for the following language if it is context-free, and if it isn't I need a proof using the pumping lemma that it is not a CFL: $$L_1=\{w_1w_2 \in \{a,b\}^* : |w_1| = |w_2|,w_1\neq w_2\}...
3
votes
2answers
958 views

Proving insertion sort using induction

A while back when I was taking a first year cs course, our professor had us write the algorithm for insertion sort in The Scheme programming language. There were also several other similar recursion ...
0
votes
2answers
99 views

Mapping between random strings?

Let us define a one-to-one function $f$ that maps binary strings of length $n$ to ternary strings of length $n$ such that if $x$ is random then $f(x)$ must be random. My question Is there an ...
4
votes
1answer
398 views

Decidable? Turing machine runs X steps for certain input?

Question is the following language decidable: {(M)|given input "aaaaa" Turing machine M will perform at least 1295 steps} I would say, yes it is. Just let the Universal Turing Machine count each ...
1
vote
1answer
254 views

Is language L context-free?

Is following language context-free? Alphabet: {a,b,c,d} L = {w | w is not in {aabbc,abc,add}} I think it is: {aabbc},{abc},{add} are all regular. Because of closure properties(Union) R = {w | w ...
3
votes
2answers
314 views

L* regular -> L regular?

If language L* (Kleene Star) is regular, does it imply that L is also regular?