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
3answers
186 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
150 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
209 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 ...
2
votes
2answers
184 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
166 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
228 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
1k 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 ...
8
votes
5answers
524 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
148 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 ...
0
votes
3answers
189 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: ...
6
votes
4answers
8k 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
148 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
123 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 ...
5
votes
1answer
357 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 ...
8
votes
4answers
498 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 ...
11
votes
4answers
793 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 ...
1
vote
1answer
209 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
205 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
163 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
447 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 ...
3
votes
2answers
375 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 ...
8
votes
3answers
4k 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
253 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
456 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 ...
5
votes
1answer
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 ...
4
votes
2answers
847 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}$ ...
9
votes
1answer
621 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
208 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
3k 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
320 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
270 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) = ...
6
votes
2answers
416 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
671 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 ...
3
votes
1answer
336 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
576 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
889 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 ...
13
votes
1answer
14k views

Recognizable vs Decidable

What is difference between "recognizable" and "decidable" in context of Turing machines?
1
vote
2answers
462 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 ...
9
votes
1answer
348 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 ...
3
votes
2answers
818 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
96 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
340 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
222 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
308 views

L* regular -> L regular?

If language L* (Kleene Star) is regular, does it imply that L is also regular?
3
votes
1answer
723 views

Turing machine configuration and computation history

These are a series of questions about Turing machines. First, are the number of a given Turing machine configurations (state + tape) countable? Secondly, given that a computation history is a ...
6
votes
1answer
651 views

Are there any known barriers to some approach for solving P vs. NP?

Are there any known barriers to show the following invariant (perhaps by some sort of induction)? Let $\Sigma$ be some finite alphabet with $|\Sigma| \geq 2$, let $M$ be some (deciding) deterministic ...
4
votes
1answer
313 views

Cantor–Bernstein–Schröder theorem and recursion

I am poking on a proof of the subject theorem. Given sets $A_i$ and injections $f_i:A_i\to A_{1-i}$, $i\in \{0,1\}$, theorem defines a bijection $b$ between $A_0$ and $A_1$. $b$ uses an auxilary ...
4
votes
2answers
182 views

Many one and One many reductions

I do not have enough complexity theory background, but I was wondering about the kind of reductions that we normally do to show NP-Completeness. I think all of the reductions that I have seen are ...