# All Questions

4 views

24 views

### Does an abstract machine only have one language? [on hold]

An abstract machine has a language which contains all the strings it recognize. In that sense, is it correct that an abstract machine has only one language? On a computer, there is a (unique?) ...
201 views

### Is a secondary TM sufficient to detect all loops?

Procedure: Start a secondary TM in parallel with the first, but have the second perform exactly 1 step each 2 steps the first TM performs (i.e. it runs at half speed). If the second machine ever ...
35 views

### What is the set of operations of a Turing machine?

From https://en.wikipedia.org/wiki/Abstract_machine A typical abstract machine consists of a definition in terms of input, output, and the set of allowable operations used to turn the former ...
14 views

### How to solve the following recurrence: g(n) = g(log n) + n^(1/2) [duplicate]

Doesn't fit the Master method, and I am not sure where to go from here. Thanks
27 views

### Quick method for approximate integer square roots

I'm looking for an algorithm that -- given a positive integer $n$ -- outputs a positive integer $\bar{n}$ with the following two properties: $(\bar{n}+1)^2>n$; $(\bar{n}-1)^2<n$; So we have ...
8 views

### Why having a simple multiplication loop and very good avalanche isn't enough to produce well-distributed hash values?

Modern non-cryptographic 32- and 64-bit valued hash functions, for example, lookup3, MurmurHash3 and CityHash, have quite sophisticated loops, each iteration of which include many multimplications, ...
15 views

### Master method question [duplicate]

Given the following equation: T(n)=5∗T(n/3)+4n Am I right that a = 5, b = 3, d = 4 which would fulfill case 2 of the Master Method (a < b^d), and gives O(n^d) running time, or am I missing ...
127 views

### Finite number of Turing machines running concurrently on multi-tapes Turing-machine-equivalent?

So basically, there are several (finite number of) Turing machines being able to read off and write to the same set of tapes (the number of tapes is finite, but each tape may have infinite tape ...
18 views

### Quantum Artificial Intelligence

Would anyone be able to point me in the direction of some good scholarly articles on Quantum Artificial intelligence. I have to write a research paper on the topic and I'm having trouble coming up ...
45 views

### Does the Y combinator contradict the Curry-Howard correspondence?

The Y combinator has the type $(a \rightarrow a) \rightarrow a$. By the Curry-Howard Correspondence, because the type $(a \rightarrow a) \rightarrow a$ is inhabited, it must correspond to a true ...
26 views

### Given two sequences of the same size, how many longest common subsequences can they have?

For simplicity assume that both have the same size N. the lengh of this subsequence can be at most N, so maybe it's max(C(N,1), C(N,2), ... , C(N,N))?
42 views

### A basic question about approximation algorithms for the Traveling Salesman Problem

Approximating the traveling salesman problem (TSP) within a constant factor $k$ is hard. The standard proof shows that the existence of such an approximation allows the Hamilton Cycle problem to be ...
39 views

### Is $AlwaysHalt$ recursively enumerable?

I was doing some complexity theory exercices and I came over this one: $AlwaysHalt = \{R(M) | M$ halts with all $x \in \{0,1\}^*\}$ Is $AlwaysHalt$ recursively enumerable? I would say YES and ...
11 views

### How does SARSA handle episode termination

When applied to domains that are episodic and have a "final" state but no final action, like a game, how does SARSA update the Q-values? e.g. A game agent would receive this series: ...
44 views

### Resolving ambiguity in dangling else

Initially the ambiguous grammar is as follows (with some cropped production rules): ...
49 views

### Are conditionals necessary in computation? [duplicate]

I know this question might seem weird, maybe I'm just overthinking, but this is really troubling me because I've been a computer engineer for some time now and conditionals (if statements for ...
24 views

### Ambiguous Grammar to Unambiguous Grammar

I'm wondering if somebody can please help me to understand how I go about converting this grammar to an unambiguous grammar. If you can point me in the right direction, I would greatly appreciate it. ...
84 views

### compressing a set of binary strings with fixed length

I'm looking for a data structure / algorithm to store an unordered set S of binary strings of a fixed length n (i.e. all ...
25 views

### Proving approximation ratio

We recently in computational complexity class dealt with approximation algorithms and I was wondering how one would prove a heuristic having a certain ratio in regards to the optimal version. Looking ...
18 views

### Comparing coefficients of boolean functions

Let a real polynomial representing a boolean function be $P(x_1,\dots,x_n) = \sum_{a\in\{0,1\}^n}c_ax^a = \sum_{a\in\{0,1\}^n}p(a)\prod_{i\in 1_a}x_i\prod_{j\in \bar{1}_a}(1-x_j)$ where $1_a$ is the ...
19 views

### What is difference between Oracle and SqlPlus? [on hold]

I installed Oracle 10g. There is also SQLplus in it. For starting the software we have to start with SQLPLUS. what is difference between them ? or they same or something else ?
25 views

### Karnaugh Map is this the simplest solution possible?

I'm learning to use a Karnaugh map but I'm not sure if I obtained the simplest expression possible. Have a look at this example Truth table (where A B C yield F): ...
7 views

### minimize cost and maximize quality of function in four variables

Problem: Find optimal values for four parameters which are used to tune an algorithm under the constraints of accuracy, time and memory. I have an indexing scheme used to search for the K-nearest ...
15 views

### For computer engineering student how useful are certifications? [on hold]

I hope this is the right exchange community. If it's not feel free to delete it. Right now I'm doing HP ATA connected devices: http://h10120.www1.hp.com/expertone/datacard/Certification/ATA-CDV1 ...