Skip to main content
The 2024 Developer Survey results are live! See the results

New answers tagged

3 votes

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....
AnoE's user avatar
  • 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, ...
kutschkem's user avatar
  • 480
11 votes

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 ...
orlp's user avatar
  • 13.8k
4 votes

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 ...
Bader Abu Radi's user avatar
2 votes

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 ...
Bulat's user avatar
  • 1,988
0 votes

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 ...
Owen Reynolds's user avatar
6 votes
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 ...
gnarrithas's user avatar
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 ...
Richard Balkins's user avatar
8 votes

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

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$ ...
gnasher729's user avatar
  • 31.1k
8 votes

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

Any algorithm that is infeasible to execute, within our lifetime (or within the lifetime of the solar system, etc.), is hard to consider "efficient". An exponential-time algorithm is ...
D.W.'s user avatar
  • 162k

Top 50 recent answers are included