Search Results
| Search type | Search syntax |
|---|---|
| Tags | [tag] |
| Exact | "words here" |
| Author |
user:1234 user:me (yours) |
| Score |
score:3 (3+) score:0 (none) |
| Answers |
answers:3 (3+) answers:0 (none) isaccepted:yes hasaccepted:no inquestion:1234 |
| Views | views:250 |
| Code | code:"if (foo != bar)" |
| Sections |
title:apples body:"apples oranges" |
| URL | url:"*.example.com" |
| Saves | in:saves |
| Status |
closed:yes duplicate:no migrated:no wiki:no |
| Types |
is:question is:answer |
| Exclude |
-[tag] -apples |
| For more details on advanced search visit our help page | |
Results tagged with turing-machines
Search options not deleted
user 7415
Questions about Turing machines, a theoretical model of mechanical computation capable of simulating any computer program.
2
votes
0
answers
153
views
Undecidability of the language with its elements(TM) having empty language [duplicate]
We can write a decider for the language:
$E=\{A\; |\; A \mbox{ is a DFA and } L(A)=\emptyset\}$
by marking method. Why we cannot use the same method to write a decider for the language with TM as fo …
- 589
0
votes
1
answer
232
views
Proving undecidability of the language composed of LBAs where their language is empty
As it is explained in Sipser's book, the following language is undecidable and he proves this using the computation history method.
$\qquad E = \{\langle M \rangle \mid M\ \mathrm{LBA}, L(M)=\emptyse …
- 589
7
votes
1
answer
4k
views
Deciding if a Turing machine has made a left move
In writing a decider for a machine to see if it has made a left move or not on an input of w, it is said that if we continue the computation for $|w|+N+1$ ($N$ : number of states) number of steps, we …
- 589
6
votes
1
answer
12k
views
Difference between a TM with an empty language and the one accepting empty string
If a TM(Turing Machine) accepts NO input string(even the blank), then its language is empty.
If a TM ONLY accepts the blank string(meaning that there is nothing on the tape except for the default bla …
- 589
18
votes
3
answers
26k
views
Why is this true: “There are countably many Turing Machines” [duplicate]
It is said that there are uncountably many languages but only countably many Turing Machines. Could someone make this clear to me?
And this doesn't mean that the set of TM is finite, yes?
- 589
12
votes
6
answers
46k
views
Can a Turing machine decide the language $L_\emptyset$ of machines with empty language?
Let $$L_\emptyset = \{\langle M\rangle \mid M \text{ is a Turing Machine and }L(M)=\emptyset\}.$$
Is there a Turing machine R that decides (I don't mean recognizes) the language $L_\emptyset$?
It see …
- 589