Problem Detail: Could a Universal Turing machine be set up so that it is able to ‘reprogram’ itself to ‘behave’ like any specific Turing machine without using some ‘outside’ source of info to cause it to do this? Asked By : 201044 Read More …
Category: Uncategorized
[Solved]: How is clock syncing implemented?
Problem Detail: I’m looking for an explanation or reference on the implementation of computer clock. To keep the question at the level of logical abstractions: say, we put together some combinational and sequential logic from basic gates. The role of the Read More …
[Solved]: Is Deciding Decidability Decidable?
Problem Detail: I am wondering if deciding the decidability of problem is a decidable problem. I am guessing not, but after initial searches I cannot find any literature on this problem. Asked By : sync Answered By : Rick Decker Major edit of Read More …
[Solved]: Big O running time for this algorithm?
Problem Detail: Here’s the code for the algorithm: Foo(n) lcm = 1 for i = 2 to n lcm = lcm*i/Euclid(lcm,i) return lcm The running time of Euclid$(a, b)$ is given as $O(log(min(a, b)))$ So the running time of the for Read More …
[Solved]: Big-O complexity when c is a tiny fraction
Problem Detail: Finding Big-O is pretty straightforward for an algorithm where $f(n)$ is $$f(n) = 3n^4 + 6n^3 + 10n^2 + 5n + 4$$ The lower powers of $n$ simply fall off because in the long run $3n^4$ outpaces all of Read More …
[Solved]: LR(0) parsing: how can I know sets of items corresponding to states?
Problem Detail: I’m studying LR(0) parser. But I don’t understand how sets of items corresponding to states can be calculated. I think The author would miss some information readers must know. Given the following LR(0) automaton, How the set of items Read More …
[Solved]: Conflict Driven Clause Learning backtracking clarification
Problem Detail: On the wikipedia page here it describes pretty well the CDCL algorithm (and it seems the pictures were taken from slides created by Sharad Malik at Princeton). However when describing how to backtrack all it says is “to the Read More …
[Solved]: Is there a way to compute time without system clock
Problem Detail: I was thinking about any method where we can use RAM I/O speed, to calculate time, let’s say for example: RAM transfer rate is 1000 MB/s, so when it’s half full (about 500 M Bytes written), by dividing 500 Read More …
[Solved]: How can you bound the error of an approximation without knowing the optimal solution?
Problem Detail: I been looking at this site and it says that people found solutions for TSP tours that are just 0.031% higher than the optimal tour is. Without finding the optimal tour how does they know what length it is Read More …
[Solved]: termination of two concurrent threads with shared variables
Problem Detail: We’re in a shared memory concurrency model where all reads and writes to integer variables are atomic. do: $S_1$ in parallel with: $S_2$ means to execute $S_1$ and $S_2$ in separate threads, concurrently. atomically($E$) means to evaluate $E$ Read More …
