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 37257
Questions about Turing machines, a theoretical model of mechanical computation capable of simulating any computer program.
5
votes
Accepted
Any reason why Turing Machine would prevail on recursion theory?
With Turing machines you can talk about computer concepts such as running time and space usage. This is harder with $\mu$-recursive functions.
-1
votes
Is there a complexity metric for finite state machines?
You could take the three-dimensional vector (states, transitions, symbols) as your measure of complexity.
Disadvantage: you get incomparable levels of complexity.
Advantage: you retain all the infor …
2
votes
Why do we use $\Gamma$ to denote a TM's tape alphabet?
Following up on @PartialOrder's comment, while $\Gamma$ is not used in Chomsky & Schutzenberger or in Chomsky's 1962/1963 papers on PDAs, it is used in Ginsburg and Greibach 1966 as follows:
A pus …
1
vote
Complexity of the language of all TMs $M$ such that $L(M)$ is decidable
This set is not r.e. nor co-r.e., in fact it's complete at the 3rd level of the arithmetic hierarchy ($\Sigma^0_3$-complete). This is shown in Soare's textbook.
0
votes
Problems understanding proof of smn theorem using Church-Turing thesis
So $g$ is a function such that $\Phi_{g(x)}(y)=f(x,y)$.
All this means is that $g$ on input $x$ will output (print on its tape, if you will) a program $P$ that does the following:
Code for $g(x)$:
…