A useless state in a pushdown automaton is never entered on any input string. Consider the problem of testing whether a pushdown automaton has any useless states. Formulate this problem as a language and show that it is decidable.
Show that all Turing-recognizable problems mapping reduce to ATM.
Consider the problem of testing whether a Turing machine M on an input w ever attempts to move its head left when its head is on the left-most tape cell. Formulate this problem as a language and show that it is undecidable.
Show that the PCP is undecidable over a binary alphabet, that is, over the alphabet = {0,1}.
Automata and Computability (A125)
1. Give an example in the spirit of the recursion theorem of a program in a real programming language (or a reasonable approximation thereof) that prints itself out.
Describe two different Turing machines, M and N, where, when started on any input, M outputs N and N outputs M.
Automata and Computability (A128)
Show that the function K (x) is not a computable function.
Show that, if P = NP then every language A P except A = 0 and A = * is NP-complete. See attached for full problem description.
Describe the error in the following fallacious “proof” that P NP. Consider an algorithm for SAT: “On input , try all possible assignments to the variables. Accept if any satisfy .” This algorithm clearly requires exponential time. Thus SAT has exponential time complexity. Therefore SAT is not in P. ...continues
Java Program - need to create GUI in three different steps
I have posted my JAVA inventory program so far. I need to do 3 more versions of this. I have been using JDK 1.5 to create my programs and will need help with the following versions using this same version. I put enough credits for all three problems as I feel the same person helping me along with this would be easiest, but I can ...continues
- ·
- 1-10
- ·
- 11-20
- ·
- 21-30
- ·
- 31-40
- ·
- 41-50
- ·
- 51-60
- ·
- 61-70
- ·
- 71-80
- ·
- 81-90
- ·
- 91-100
- ·
- 101-110
- ·
- 111-120
- ·
- 121-130
- ·
- 131-140
- ·
- 141-150
- ·
- 151-160
- ·
- 161-170
- ·
- 171-180
- ·
- 181-190
- ·
- 191-200
- ·
- 201-210
- ·
- 211-220
- ·
- 221-230
- ·
- 231-240
- ·
- 241-250
- ·
- 251-260
- ·
- 261-270
- ·
- 271-280
- ·
- 281-290
- ·
- 291-300
- ·
- 301-310
- ·
- 311-320
- ·
- 321-330
- ·
- 331-340
- ·
- 341-350
- ·
- 351-353
- ·
