# All Questions

42 questions
Filter by
Sorted by
Tagged with
40 views

### It is decidable whether a pushdown automaton will accept a word? [duplicate]

I'm asking myself if the problem of decide whether a push down automaton will accept a word is decidable. I would say that you can simulate a push down automaton with a Turing Machine and, if it ...
3k views

### Show that there are infinitely more problems than we will ever be able to compute

I was looking at this reading of MIT on computational complexity and on minute 15:00 Erik Demaine embarks on a demonstration to show what is stated in the title of this question. However I cannot ...
107 views

### Prove Halting on all Inputs is not in RE simulation

I don't understand why when proving if Halting on all inputs problem si not in RE using the complement of the halting problem, I have to take a turing machine and simulate the machine M(the machine ...
76 views

120 views

267 views

### How to prove or disprove that f is computable?

If $f(x_1,\dots, x_n)$ is a total function that for some constant $K$, $f(x_1,\dots, x_n) \leq K$ for all $x_1,\dots, x_n$ then $f$ is computable. I want some hints on how to prove/disprove the ...
591 views

### If a predicate is not computable, what can be said about its negation?

Doing the following exercise: Let $\overline{HALT(x,y)}$ be defined as $\overline {HALT(x,y)} \iff \text{program number y never halts on input x}$ Show that it is not computable. Just ...