Skip to main content

Questions tagged [infinity]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
0 votes
5 answers
2k views

If the set of Turing machines is countably infinite, how can a Turing machine always have a finite set of states?

I have only begun studying this subject and have only completed the first few chapters of the Elements of the Theory of Computation. I have seen the answers (on this site and elsewhere) saying that ...
Wisdom Iwueze's user avatar
2 votes
3 answers
71 views

can a model of computation with infinitely many states be nontrivially decidable?

i'm trying to make a game in which the player faces an infinite (finitely specified) series of enemies and has to specify a strategy that provably defeats all of them (ie defeats enemy n in finite ...
Silver's user avatar
  • 417
6 votes
1 answer
280 views

Are any "standard" complexity classes uncountably infinite?

(This is a somewhat fuzzy question.) I believe that most of the "standard" complexity classes that one comes across in complexity theory are countably infinite, because they are defined in ...
tparker's user avatar
  • 1,116
0 votes
2 answers
59 views

Can a program that terminates have a running time of infinity? (Or not have an upper bound)

Can we have an algorithm that takes some input and does something random to it (in such a way that the algorithm does terminate) which does not have a worst-case running time upper-bound? A (non-)...
proof-of-correctness's user avatar
0 votes
1 answer
318 views

Sets of problems in different models of computation and cardinality

In university, I was taught the computational model hierarchy given in the following figure: https://devopedia.org/images/article/210/7090.1571152901.jpg Essentially, Pushdown Automata (PDA) can solve ...
Enk9456's user avatar
  • 19
3 votes
2 answers
1k views

Determining if an NFA accepts an infinite language in polynomial time

Can we determine in polynomial time if the language accepted by an NFA is infinite? The case of DFA is simple, but converting an NFA to a DFA may take exponential time. Also, I ran into this post, ...
Avi Tal's user avatar
  • 339