5
No. The difference between a Turing machine and a finite automaton is in the amount of available work space:
Finite automata are equivalent to Turing machines with finite tapes.
Indeed, any finite automaton can be encoded as a Turing machine that requires no additional work tape. Conversely, a Turing machine whose work tape has finitely many cells has a ...
4
Your function is well-defined, that is, total. The value of $f(n)$ is the maximum of the finite set $\{g_1(n), \ldots, g_{w(n)}(n)\}$. The maximum of a finite set of numbers always exists.
Your function is computable iff $w$ is bounded. Suppose first that $w$ is not bounded, and assume for the sake of contradiction that $f$ were computable. Then $h(n) = f(n) ...
3
Randomness is not the same as non-determinism -- at least, not the non-determinism that is referred to when people talk about non-deterministic Turing machines.
See Can an algorithm be truly non-deterministic?, Differences and relationships between randomized and nondeterministic algorithms?, https://cstheory.stackexchange.com/q/632/5038, Are ...
2
It depends what you mean by "pure". Without knowing what you mean by it, it seems hard to say. See https://en.wikipedia.org/wiki/Pure_function for one possible meaning. That notion relates to the input-output behavior of the system, and Turing machines and finite-state automata can be viewed as systems that meet those requirements.
It is true ...
2
You can of course simulate a non-deterministic TM in this way.
Is it polynomial time? It depends what you mean by that, but as a first approximation, the answer is no. The total amount of computation performed -- the total running time, summed across all threads -- will be exponential in general. For instance, the amount of energy used for this ...
2
TMs accept words as input.
What this paragraph is saying is that you cannot encode arbitrary languages as finite strings (aka words), and hence you cannot easily describe a property over languages themselves (for instance, a property of "all languages that contain the empty word", is a property over languages).
Afterwards it represents a way to ...
1
Typically, no, this is not possible. It depends on how the infinite set is represented. (I'm assuming it's a set of integers.)
The usual way to represent a possibly-infinite set $S$ is as a Turing machine $M$: $M$ enumerates all the elements of $S$. For this representation, it is uncomputable to determine the maximum element of $S$. That is, on input $\...
1
First hint: construct a TM that converts the input into a unique natural number
Second hint: encode the language directly in the turing machine, by specifying which natural number is considered a part of the language and which one isn't.
1
Admittedly, the sentence you give is indeed a trifle obscure. Simply said, it is saying that if we have a property of a language, like "any string in the language has odd length", we can't hope to recognize the property by using a TM that will iterate over all strings of all possible languages to test, since that would clearly be an infinite input, ...
1
Here is an algorithm that can be implemented with a Turing machine using a small number of states, and that only accepts inputs that I suspect are likely to look complicated to most humans. Let the bits on the tape be $T[1,\dots,n]$:
For $i:= 1,2,\dots,8$:
For $j:= 3,4,\dots,n$:
Set $T[j] := T[j] \oplus (T[j-1] \land T[j-2]) \oplus C[i]$.
For $j:= n-2,n-...
1
The answer depends on the coding of $n$.
The set $\{(M,x,1^n) | \text{ TM } M \text{ accepts }x \text{ within } n
\text{ tape space } \}$ is $PSPACE$-complete. But the set $\{(M,x,n) | \text{ TM } M \text{ accepts }x \text{ within } n
\text{ tape space } \}$ where $n$ is binary coded is $EXPSPACE$-complete.
1
If H(x,x) goes into an infinite loop, then that fact already proves that H does not solve the halting problem. If H solves the halting problem, then it never goes into an infinite loop.
If we are trying to figure out whether it's possible to solve the halting problem, we can ignore all the functions that sometimes enter infinite loops. They obviously don't ...
Only top voted, non community-wiki answers of a minimum length are eligible