Ben
• Member for 9 years, 10 months
• Last seen more than a month ago
• Melbourne, Australia

No, it would be more powerful. The transition function would no longer be finite, and that buys you a lot of power. With an infinite alphabet, you can encode any input item from an infinite set in ...

To elaborate slightly on the "it's impossible" statements, here's a simple proof sketch. We can model algorithms with output by Turing Machines which halt with their output on their tape. If you want ...

An equivalent definition of NP is that it consists of all problems that are decidable (not just verifiable) in polynomial time by a non-deterministic Turing machine. NTMs are known to be no more ...

The basic difference between the C++ statement x = a + b and the Python statement x = a + b is that a C/C++ compiler can tell from this statement (and a little extra information that it has readily ...

As spotted by svick, the first issue with the code in the OP is that names beginning with upper-case letters are variables in Prolog. So admit(CP) :- admit(AD) is equivalent to attend(X) :- attend(Y), ...

If it were this language: $B = \{\; 0^k1u10^k \mid k ≥ 1 \text{ and }u ∈ Σ^*\;\}$ you'd be in trouble. $B$ is not regular. The key problem is that when trying to recognise strings from $B$, you ...

Turning Machines model computation, and don't have a concept of interaction. In that sense a machine that supported interaction with an outside system can do things a Turning Machine can't. But the ...

There are unfortunately as many techniques to prove functions uncomputable as there are to prove things in general, so there's no comprehensive doctrine for how you should approach this. Note that ...

I think most likely the explanation for some authors using "logic error" and "semantic error" interchangeably and some authors drawing a distinction is simply that they don't have a precise ...

The halting problem is undecidable of course. This implies that there is at least one program for which we cannot decide whether it halts or not. The undeicidability of the halting problem actually ...

A reduction from A to B shows that A is "no harder" than B in some sense. We call it a reduction because it reduces the problem of solving A to the problem of solving B. This is a usage of the word "...

The condition that $y$ has length at least one is to avoid a triviality. If you allow the length of $y$ to be zero then for any language you can divide each word in the language into $xyz$, such that $... View answer 4 votes An interrupt is an "unusual" event that happens which needs to be processed immediately, regardless of whatever else is going on. I say "unusual" in quotes, because they're not necessarily unexpected ... View answer 3 votes The definition of the class NP-hard is that a problem is NP-hard if every problem in NP can be reduced to it in polynomial time. The definition of the class NP-complete is just the problems that are ... View answer 3 votes Usually downcasting is what you do when the statically known knowledge the compiler has about the type of something is less specific than what you know (or at least hope). In situations like your ... View answer 3 votes I'm a little confused by your quote. There are two equivalent definitions of the NP complexity class in terms of Turing Machines: The class of problems for which a deterministic verifier exists ... View answer Accepted answer 3 votes A reduction is a transformation from an unknown but easier problem to a harder problem but already known. If the harder problem is solvable, so is the easier one. Otherwise, it's not. Your ... View answer Accepted answer 3 votes I think your "non-trivial" property would need to be a property of sets of triples, not of triples themselves; i.e. you need that there are an infinite number of sets of triples that satisfy and do ... View answer 3 votes Many others have mentioned that Type-1 languages are those that can be recognised by linear bounded automata. The halting problem is decidable for linear bounded automata, which in turn means many ... View answer 2 votes You can construct a recognizer that simply simulates M on w and then simulates M on$w^R\$. This will halt in finite time for all that are in A (by definition), and then you can accept if the first ...

It matters what is actually happening in the code. The following pseudocode is O(1) loop_factor = input() for x between 0 and loop_factor(): for y between 0 and loop_factor(): terminate ...