The 2024 Developer Survey results are live! See the results

# Tag Info

## New answers tagged terminology

### Do programs within which a computable function runs a random number of times always halt, as in the halting problem?

If you are asking about pseudo random numbers, then your example is decidable: a PRNG is, by definition, not random at all, but if starting from the same seed is guaranteed to repeat exactly as before....
• 1,303
1 vote

### Do programs within which a computable function runs a random number of times always halt, as in the halting problem?

Pseudo-random number generators (at least the ones I know of, and in particular this one) output a fixed cycle of numbers, with the starting point determined by the seed. So unlike true randomness, ...
• 480

### Do programs within which a computable function runs a random number of times always halt, as in the halting problem?

The Halting Problem is defined on deterministic Turing machines, which do not have randomness. There is a probabilistic version of the Halting Problem for probabilistic Turing machines, which asks if ...
• 13.8k

### Naming Turing machines paired with input

I don't think there is an established name for such pairs, or at least I am not aware of one. In fact, I don't think it would be very helpful or informative to give them names -- as you mentioned, in ...
• 3,286

### Classification of efficient and inefficient algorithms and the scientific reasoning behind them

Even aliens can't break https://en.wikipedia.org/wiki/Limits_of_computation (at least the aliens I know). In particular, we are already within 10^5 times of the minimal energy required for ...
• 1,988

### Classification of efficient and inefficient algorithms and the scientific reasoning behind them

As far as references, you're looking for big-O notation. It groups the "efficiency" of algorithms into things like $O(\log n)$, $O(n^2)$, $O(n^5)$ and $O(2^n)$ (that last being exponential ...
Accepted

### Classification of efficient and inefficient algorithms and the scientific reasoning behind them

One of the key ideas of algorithm analysis is to be able to assess how the running time changes as the size of the input changes. Consider a list of $n$ elements. Saying an algorithm runs in linear ...
• 359
1 vote

### Are dictionaries and associative arrays the same thing?

Depends on the language. On the abstract level of this computer science concept, they are fundamentally synonyms. They are the same thing. One of those concepts where multiple people came up with ...
An algorithm or implementation is “inefficient” if it takes longer than necessary. Some problems are hard. There are no fast algorithms because the problem is so hard. An algorithm that takes $2^n$ ...