Questions tagged [turing-machines]
This tag is suited for questions involving Turing machines. Not to be confused with finite state machines and finite automata.
0
votes
0answers
74 views
Does/Can a “function” exist that can “return” “any” “number series”?
I am really a novice at Math and am interested in the existence of such function as I think it could be really useful for some experimentation in machine learning.
My question is, does/can a "...
1
vote
2answers
36 views
Having trouble determining what Turing machine evaluates?
While learning about Turing machines, I've stumbled onto a problem that I'm not sure how to solve. I've put a lot of work into trying to find the solution, any help would be appreciated.
The problem ...
1
vote
1answer
17 views
Five shortest strings from language $ L = \{0^{i}1^{i}| i \in \mathbb{N} , i > 0\}$
I am studying for an upcoming exam, with an example question being.
Consider the following language,
$L = \{0^{i}1^{i}| i \in \mathbb{N} , i > 0\}$
Over the alphabet
$A = \{0,1\}$
What are the ...
2
votes
1answer
49 views
Is Langton's Ant really Turing Complete
I recently watched a Numberphile video about Langton's Ant (and the extra footage). They mention that the ant always ends up creating a highway at some point in all the initial board configurations ...
0
votes
0answers
11 views
Prove the probability of which a hash function is collision-free
Suppose $H = \{h_1, ..., h_T\}$ be a family of pairwise independent hash functions mapping $\{0, 1\}^n$ to $\{0, 1\}^{n/2}$. Let $M = \frac{2^{n/4}}{10}$ and let $x_1, ..., x_M$ be any M distinct ...
0
votes
1answer
54 views
Turing Machine for vertex cover
Give a polynomial-time Turing Machine which, given
a graph G and an integer k as input, will halt and output a vertex cover of G of size at
most k — that is, it halts with the encoding of an actual ...
1
vote
0answers
60 views
Classify Turing Machine as Decidable, Co-recognizable, Recognizable
Consider the language
L = {: M is a TM and M visits its start state at least twice when executed on ε}.
Prove L with respect to decidability, recognizability, and co-recognizability.
I think the ...
0
votes
0answers
48 views
How can I estimate Turing machine running time?
I try to evaluate working time of Turing machine. I understand, I have to calculate number of steps used in every stage. My problem is: how can I know, how many steps used in every stage, for example, ...
0
votes
0answers
13 views
How can I prove the following question?
For every time constructible function T, if L is in TIME(T(n))(or more specifically D-TIME) class, then there exists an oblivious Turing Machine M that decides L in O(T(n) log T(n)) time.
0
votes
0answers
39 views
Deterministic Turing machine for the language L = {x ∈ {0, 1} ∗ | x is not of the form 0w1w for w ∈ {0, 1} ∗}.
All right so, for this I don't need to graphically show the Turing machine, but rather just describe the process.
I feel like I can do this on my own, but I'm having a little trouble starting. I'm ...
0
votes
1answer
96 views
Prove that the following language is decidable / undecidable
Part A)
Prove that the following language is decidable: Input: The description of a DFA A.
Output:
YES if A accepts the empty string.
NO if A does not accept the empty string.
I am struggling ...
0
votes
0answers
9 views
Why do results shown by diagonalization relativize?
my textbook mentions: "Using an oracle $O$ to show $L \neq B$ then for every oracle $X$ $L^X \neq B^X$. So this fact isnt very intuitive to me. Can someone please help ?
9
votes
1answer
331 views
Hopping to infinity along a string of digits
Let $s$ be an infinite string of decimal digits, for example:
\begin{array}{cccccccccc}
s = 3 & 1 & 4 & 1 & 5 & 9 & 2 & 6 & 5 & 3 & \cdots
\end{array}
Consider ...
1
vote
2answers
47 views
Ordering of Turing machines?
I am new to Turing Machines. As in I’ve been reading about them over the last two days. So I am not very knowledgeable at this moment.
I was also reading about the Kleene’s O system of ordinal ...
1
vote
1answer
18 views
$Show\:that\:B_A=\left\{w\in \sum ^{\ast }:\:\exists \:x\in \:A\:s.t\:\left|x\right|\le \left|w\right|\right\}\:is\:decidable\:$
$A\:is\:some\:language\:over\:\sum.\\Show\:that\:B_A=\left\{w\in \sum ^{\ast }:\:\exists x\in A\:s.t\:\left|x\right|\le \left|w\right|\right\}\:is\:decidable\:$
I thought to show a non-deterministic ...
0
votes
0answers
45 views
what is the mapping reduction of $A_{TM}$ to $\overline{CF_{TM}}$
first post here :)
I am trying to find a reduction from $A_{TM}$ to $\overline{CF_{TM}}$.
definitions:
$CF_{TM}\:=\:\left\{<M>| M\:is\:a\:TM\:and\:L\left(M\right)\:is\:a\:context-free\:...
0
votes
0answers
21 views
Proving Turning Decidable's
Prove that L CFG \ L RG is Turing-decidable, where
L CFG = {< G, w > G is a CFG that generates string w}.
L RG = {< G, w > G is a regular grammar that generates string w}
In relation ...
0
votes
1answer
48 views
Enumerator printing out strings from a language
Write down the algorithm of an enumerator that prints
out EXACTLY ONCE every string in the language L = {7m+ 2 |
m ∈
N} over the alphabet A = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}.
In regards, to the ...
0
votes
0answers
10 views
How to show that if $L(M) \in NP$?
An M deterministic Turing Machine finishes with an n long input in $ \left( n^{100} + 2^{\log{n}} \right)n^2 $ steps. Show that if $L(M) \in NP$.
I'm having problem with this exercise. Could someone ...
0
votes
1answer
34 views
let $L = \{\langle M \rangle \mid M \text { is a TM, } \forall x \in L(M), x^R \notin L(M)\}$. Prove/disprove $L\in RE \backslash R$
let $L = \{\langle M \rangle \mid M \text { is a TM, } \forall x \in L(M), x^R \notin L(M)\}$
($x^R$ is the reverse of $x$)
I need to determine and prove whether $L\in R , L\in RE \backslash R, \...
0
votes
1answer
28 views
is there a linear bounded automaton the decides $A_{nfa}$?
first post here :)
I was wondering, since regular languages are context sensitive, and since linear bounded automatons can act as an acceptors for context sensitive language, is it possible or is ...
3
votes
1answer
39 views
Diagonal argument applied to computable numbers
Upon applying the Cantor diagonal argument to the enumerated list of all computable numbers, we produce a number not in it, but seems to be computable too, and that seems paradoxical.
For clarity, ...
3
votes
1answer
88 views
What does it mean for a number to be independent of ZFC?
Since the definition of the Busy Beaver function by Radó in 1962, an interesting open question has been what [is] the smallest value of $n$ for which $BB(n)$ is independent of ZFC set theory.
Source: ...
0
votes
0answers
10 views
Prove the languages |L<M>| = 2 and |L<M>| $\not=$ 2 to be non-Turing recognizable or non-recursively enumerable
I am trying to prove the non-recursively enumerable property of two languages.
L = {$\langle M \rangle$: |L$\langle M \rangle$| = 2}. and
L = {$\langle M \rangle$, |L$\langle M \rangle$| $\not=$ 2}.
...
0
votes
0answers
15 views
How to prove {e: L($M_e$} is decidable} is not Turing-recognizable?
I have reduced {e:$M_e$ accepts e} to this one. But I failed to reduce in the other direction.
And I don't know if there is an algorithm to solve this.
Thank @Noah Schweber who tells me it's not ...
0
votes
0answers
21 views
L = {$(n,w)$ $w$ is a binary representation of the n-th fibbonacci number} membership decision problem
I am a student currently studying Computational Models. I still don't have a full understanding of the subject and was wondering about languages of the form
$L = \left \{(n,w) | f(n) = w \right \}$ ...
0
votes
1answer
133 views
Difference of two decidable languages?
I've been learning about TMs in class lately and we talked about the decidability of two languages by union or intersection. I was wondering if you have two decidable languages, L1 and L2, is their ...
0
votes
0answers
111 views
Complexity of a copy and reverse Turing Machine
I have a turing machine, that appends a reversed copy of a string to the end of the string. The alphabet of the TM is {a, b}.
Copy & Reverse TM
How can I prove the time complexity of this Turing ...
0
votes
0answers
17 views
Turing Machines recognizing the same language
Is it possible for two turing machines that take different types of inputs, for example $\langle M,w\rangle$ and $\langle M\rangle$, to recognize the same language?
1
vote
0answers
65 views
What rule allows to determine the symbol on an $i$-th cell of the tape of an Infinite Time Turing Machine at any limit stage?
Assuming that $s$ denotes a particular symbol that can appear on the tape, $\alpha$ denotes any limit ordinal such that $\alpha \ge \omega$ and $C_i[\tau]$ denotes the symbol on the $i$-th cell of ...
1
vote
1answer
51 views
Can we enumerate finite sequences which have no halting continuation?
Note: this is a cross-post from CS.SE, since I haven't gotten an answer there.
I am trying to deepen my understanding of the relationship between the Halting Problem and Godel's Completeness Theorem (...
-1
votes
1answer
20 views
$\delta:Q\times\Gamma\to Q\times\Gamma\times\{L,R\}$: how to convert this statement in $f(x)$ form?
$\boldsymbol{\delta:Q\times\Gamma\to Q\times\Gamma\times\{L,R\}}$: this equation represents the transition function of deterministic Turing machine.
How can i convert it in $f(x)$ form, like $f:x\...
1
vote
1answer
81 views
How to prove or disprove that a machine is Turing Complete?
Given a set of operations machine can perform, how to prove or disprove it's Turing Completeness? Is the definition of a set of operations and corresponding state changes is enough or should I add ...
0
votes
1answer
14 views
Specify a decisive Turing machine that calculates the following function $f$.
Specify a decisive Turing machine that calculates the following function $f$: $$\small f:\{a,b\}^*\to\{a,b\}^*\textrm{ with }
f(w)=
\begin{cases} (bba)^{3\cdot\#_b(w)}& \text{if } \#_a(w) \text{ ...
2
votes
1answer
71 views
Where is the theorem related to the construction of countable admissible ordinals by Turing machines with oracles?
Wikipedia contains the following information in the article "Admissible ordinal":
By a theorem of Sacks, the countable admissible ordinals are exactly those constructed in a manner similar to the ...
0
votes
0answers
54 views
Correctness proof: induction on sequence of steps, need a stronger claim?
Im trying to prove the correctness of the construction proposed in this CS-SE answer: a two stack PDA that simulates a Turing Machine. By "correctness" i mean to prove more or less formally that we ...
6
votes
1answer
160 views
Is classical Euclidean geometry Turing complete?
By "classical Euclidean geometry" I don't mean the study of $\mathbb R^2$ with the Euclidean metric, or a model of Hilbert's Grundlagen axioms, or the study of those properties of $\mathbb R^2$ that ...
0
votes
0answers
25 views
does the language 𝐿 = {< 𝑀1 >, < 𝑀2 >: 𝐿(𝑀1 ) ⊆ 𝐿(𝑀2)} is in co-RE?
i was asked to determine if its in RE and if its in co-RE.
well i think its easy to say the language is not in RE but i was wondering if this language is in co-RE.
so the question is if $\overline{L}$...
7
votes
2answers
65 views
Is it possible to put a topology on Turing-recognizable languages to express density among all the languages?
In a Calculability and complexity course I had at univeristy, we proved that there exist languages that are not Turing-recognizable basiclly using Cantor's diagonal argument (the set of all languages ...
0
votes
0answers
44 views
How can I prove that binary multiplication decision problem is solved in O(logn) space?
I can prove this if I use a NTM Turing Machine, but it is required to use a two-taped DTM, while taking into account only the space of the second "work tape"
0
votes
0answers
14 views
Is there a name for this type of turing machine?
I'm considering the turing machines with the following form: $(Q,\Gamma,b,\Sigma,\delta,q_0,F)$ where the tape symbols,$\Gamma$ are $\{0,1\}$, so the input symbols, $\Sigma$ must be $\{1\}$ and the ...
1
vote
1answer
33 views
Decision function uncountable, why?
Good morning guys,
I'm a new user of StackExchange, and I have already found here:
Set of decision functions are uncountable
However, I do not really understand the answer. I'm a student of Computer ...
1
vote
1answer
44 views
Finding languages such that $L_1\subset L_2\subset L_3$ where $L_1,L_3\notin$ RE and $L_2\in$ R [duplicate]
I am struggling to find such languages $L_1$, $L_2$, and $L_3$ such that
$L_1\subset L_2\subset L_3$
where $L_1,L_3\notin$ RE and $L_2\in$ R.
I know they exist, I need help finding them.
0
votes
1answer
73 views
Minimum Number of states turing machine
I think my question is rather simple, but I can't wrap my head around it. In "The (new) Turing Omnibus" on page 266, the author writes:
[...], and let A be a [Turing-]machine that converts a blank ...
0
votes
1answer
62 views
Finding languages such that $L_{1} \subseteq L_{2} \subseteq L_{3}$ where $L_{1}, L_{3} \notin \mathbb{R}$, $L_{2} \in \mathbb{R}$
I am struggling to find such languages $L_{1}$, $L_{2}$, and $L_{3}$ such that
$$
L_{1} \subseteq L_{2} \subseteq L_{3}
$$
where $L_{1}, L_{3} \notin \mathbb{R}$ and $L_{2} \in \mathbb{R}$.
I know ...
1
vote
0answers
49 views
Definition of partial function using predicate that is possibly undecidable
I am reading Kleene's "Mathematical Logic" $2002$ pp 242-246.
Let $T(i,a,x)$ stand for: $i$ is the index of a Turing machine (under particular enumeration) which when applied to $a$ as an argument ...
1
vote
0answers
25 views
exhibiting a turing machine and a λ-term of a boolean function
I have a funtion f: BOOL ⇒ Bool, sich that f(x,y) is true when x=y and false otherwise. Im trying to exhibit a touring machine and a lambda term. for the second part I know that in boolean logic, x ⇒ ...
1
vote
0answers
35 views
How to prove that models of indirect and direct RAM machines are equivalent?
as in the title, I am looking for a formal proof how to show that models of indirect and direct RAM (random-access) machines are equivalent.
I would really appreciate your help.
4
votes
1answer
156 views
Turing machine with read only part and finite tape
Given a Turing machine whose input part is read only , and in addition to the input part has a finite tape of length K, prove that this is equivalent to a DFA.
I tried to find some bound for the ...
1
vote
1answer
138 views
What is the source of formal descriptions for large uncomputable ordinals clockable by Infinite Time Turing Machines?
I can imagine the process of analyzing the computation of an ITTM at any limit stage denoted by $\alpha$ if $\alpha$ is a computable ordinal: basically, we take the description of some standard Turing ...
