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
1answer
21 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
32 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
76 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
7 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
13 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
20 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
47 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
79 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
14 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
59 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
49 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
19 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
61 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
12 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
69 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
48 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 ...
2
votes
0answers
48 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
24 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
61 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
36 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
13 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
31 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
43 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
43 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
58 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
43 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
31 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
118 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
136 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 ...
27
votes
5answers
3k views
Exactly when and why can a Turing-machine not solve the halting problem?
I perfectly understand and accept the proof that a Turing-machine cannot solve the halting problem.
Indeed, this is not one of those questions that challenges the proof or result.
However, I feel ...
0
votes
1answer
117 views
What exactly does it mean for an Infinite Time Turing Machine to reach stage $\omega$ (and limit ordinal stage)?
The paper “Infinite Time Turing Machines” contains the following information:
At each step of computation, the head reads the cell values which it overlies, reflects on its state, consults the ...
0
votes
1answer
59 views
Ultratasks in the ITTM Model
[Note: I have not previously seen a definition that relates Beth numbers to Supertasks, however my intuition is that one may exist]
A supertask is a countably infinite sequence of operations that ...
0
votes
1answer
34 views
Why does a Turing machine take $n^k$ steps for computing an input?
I was reading about Cook's Theorem for Turing machine. In its proof, it is said that the Turing machine would take at most $n^k$ steps (where $k$ is an integer and $k > 0$) to compute an input of ...
0
votes
1answer
33 views
How to prove that class of “recursive” and “recursively enumerable” languages are not equal?
I would like to formulate a formal proof for showing that the classes of recursive and recursively enumerable languages are not equal.
I know that recursive languages are accepted by Turing machines ...
0
votes
0answers
48 views
Number of divisors of a number - in NP?
I'm trying to show that the language $\{(m,n) | m \space \text{has exactly} \space n \space \text{divisors}\}$ is in NP.
The input $(m,n)$ is in binary.
The non-deterministic Turing machine for the ...
3
votes
0answers
27 views
A version of a Turing maching that can cut out and/or remove tape squares
I would like to know if in the literature there have been considered versions of Turing machines that, instead of changing the content of one tape square at a time are allowed to perform more general ...
2
votes
1answer
37 views
Undecidability of: $|w \in L| \geq 1, L=\{w \in \{0,1\}^*|a_0·\#_0(w)+a_1·\#_1(w)- a_1a_0=0\}$
Let $a_0, a_1 \in \mathbb{N} \setminus \{0\}$ and $L=\{w \in \{0,1\}^*|a_0·\#_0(w)+a_1·\#_1(w)- a_1a_0=0\}$ . Let's assume problem $P$ that, language of Turing machine accepts at least one word from ...
1
vote
2answers
64 views
Can a hypercomputer solve random sequences? [closed]
I would love to know the answer to this question. Lets have a hypercomputer which is capable of doing an uncountably many computational steps in finite time with infinite memory. Now could such a ...
2
votes
1answer
43 views
Does my solution show that the language is uncomputable by applying rice's theorem?
If p is a Turing machine then L(p) = {x | p(x) = yes}.
Let A = {p | p is a Turing machine and L(p) is a finite set}.
Is A computable? Justify your answer.
So I'...
1
vote
2answers
63 views
What is a computable function?
If $f:\Sigma^* \to \Sigma^*$ is function, and $\exists$ a Turing machine which on the input $w\in\Sigma^*$ writes $f(w)$, $\forall w\in\Sigma^*$, then we call $f$ as computable function.
But in ...
0
votes
0answers
11 views
Lipschitzness on a space of Turing Machines
I am trying to prove that $l$ is Lipschitz bounded and convex on the set $Z$ of all turing machines
For some $h \in (0,1)$ and $T \in Z$
$\ell(h,T) = h \ell(0, T) + (1-h)\ell(1,T)$
where $\ell(0,T)$ ...
0
votes
0answers
85 views
Problem with this generalised Rice's theorem
$S$ is a subset of the class of all recursively enumerable languages over some finite symbols then $S$ is recursively enumerable iff
If $L$ is in $S$ and $L'$ is a language such that $L ⊆ L'$ and $L'$...
1
vote
1answer
66 views
Can I give undefined ($\perp$) as an argument to my function?
Hopcroft & Ullman (1979) say that a function $f(x)$ is undefined when $f$ is not defined for $x$ and they use (I think) the $\perp$ symbol to denote that.
My question is: since I can use $\perp$ ...
3
votes
0answers
27 views
Is a Turing Machine with access to an entropy source “more powerful” than an ordinary TM?
I'm wondering whether a Turing Machine with access to a random number generator is equivalent in power to an ordinary Turing Machine. The RNG is implemented here as a privileged instruction that reads ...
1
vote
0answers
94 views
Turing machine that accepts strings $w$ of ${a,b,c}$ where $w = a^i b^j c^k$ and $i\ge j$, $j\ge k$, and $i,j,k \ge 0$
Basically a Turing machine that accepts strings that look something like aaabbcc or even aabc or abc. There just has to be at least one of each letter and they have to be in that order and there needs ...
1
vote
2answers
62 views
Functions corresponding to Turing machines that might not halt but consume bounded tape
$ \renewcommand{\N}{\mathbb{N}} $
$ \renewcommand{\def}{\stackrel{def}{=}} $
$ \renewcommand{\symstart}{\text{start}} $
$ \renewcommand{\symhalt}{\text{halt}} $
$ \renewcommand{\boundedLoop}{\text{...
0
votes
0answers
11 views
Reference for type-2 Turing machines and does the limit lemma hold?
I am looking for a good reference on the theory of type-2 Turing machines (infinite input tape, finite output tape say). In particular, whether the Shoenfield Limit Lemma holds in this case and ...
2
votes
0answers
58 views
Hypertask, Arithmetical hierarchy and beyond
Good day,
I would love to ask this question. Lets have a hypercomputer capable of doing a hypertask, that is performing uncountably many computational steps in finite time(the same amount of steps ...
1
vote
0answers
43 views
Is there a good notion of hypercomputation which allows inaccessible-length computations?
Good day,
I would like to ask, whether a good notion of hypercomputation which allows inaccessible-length computations exists. I am familiar with a notion of supertask, which is a countably many ...
