Questions tagged [turing-machines]
This tag is suited for questions involving Turing machines. Not to be confused with finite state machines and finite automata.
1,001 questions
0 votes
0 answers
64 views
Proving Inf is 1-reducible to Tot
I am currently working on a proof that $\mathrm{Inf}\leq_1\mathrm{Tot}$, where $$\mathrm{Inf}=\{e:\mathrm{Dom}\,\varphi_e \text{ is infinite}\} \quad \mathrm{Tot}=\{e:\varphi_e\text{ is total}\}$$ (...
- 329
3 votes
1 answer
101 views
Speaking constructibility of a natural number in ZFC
This question is related to this earlier question Precise meaning of a natural number being independent of ZFC. Now my intension is to formalize the sentence “we can construct a natural number $n$ ...
- 650
2 votes
0 answers
93 views
Is there a Turing complete cellular automaton buidable from XOR and 1?
I recently learned in my last question that rule 110, while being Turing-complete, can be built from a set of falsity-preserving functions (such as $\{\lor, \oplus\}$) which isn't functionally ...
-2 votes
1 answer
159 views
What are the axioms of Python programming language? [closed]
My understanding is that Python is "Turing complete" which mean they work on the same axioms (or by first order logic equivalent) as a theoretical Turing machines (https://en.wikipedia.org/...
- 15
0 votes
0 answers
43 views
Algorithm that determines if an input string is in the language
In a practice midterm question, there's the following question. I am confused about why can't we just return the negation of the output of the FSA, instead of converting it into a Turing Machine. (d) ...
- 21
1 vote
0 answers
80 views
Simple dynamical system simulating a Turing machine?
Given some Turing machine $M$ computing, say, a total function (so it halts on all inputs), I want a simple and direct way of encoding this Turing machine into some dynamical system over some subset ...
- 619
0 votes
1 answer
59 views
Is the polynomial bound on the certificate in the verifier definition of the complexity class NP redundant?
All formal verifier-based definitions of NP that I can find online ask for a polynomial bound on the certificate. For example, the Wikipedia page for NP defines: "A language $L$ is in NP if and ...
-1 votes
3 answers
294 views
How to count in Turing Machine [closed]
I want to build a Turing machine that recognizes language $L = \{a^{2n}\mid n \geq 0\}.$ And I thought of an algorithm that writes a string next to the input and doubles its size with each iteration: ...
- 13