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
13 views
Is there always a reduction function between two languages in R? [on hold]
I believe this sentence to be true, but i could not manage to prove it.
2
votes
0answers
35 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
22 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
54 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
18 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
12 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
28 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
39 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
21 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
54 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
39 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
21 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
29 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
76 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
97 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
4answers
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
109 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
52 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
23 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
26 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
42 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
26 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
36 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
42 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
55 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
72 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
25 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
83 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
53 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
54 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
42 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 ...
5
votes
1answer
91 views
Does there exist a strict numeric measure of the strength for any set theory (relative to a corresponding proof-theoretic ordinal)?
I have found the following quote ( source ):
The proof-theoretic ordinal of any theory is less than $\omega_1^{CK}$.
But if all these proof-theoretic ordinals are recursive and below $\omega_1^{...
0
votes
1answer
38 views
Halting Problem with True/False Answer
The simplified explanation to the Halting Problem relies on the contradiction in if you have a Turing Machine H that can decided if a program ...
-2
votes
1answer
40 views
Write a procedure to demonstrate that $L$ is recursively enumerable.
Let $L$ be a recursive language. Is $L$ recursively enumerable? If yes, write a procedure that demonstrate it. If not, write a counterexample.
Given that $L$ is recursive we know there exist an ...
1
vote
2answers
76 views
How exactly does the oracle for a well-order of order type $\omega_1^\text{CK}$ operate?
The concept of an oracle for Turing machines assumes that the oracle answers Yes/No to a particular question $Q$, assuming that $Q$ is formulated as a bitstring on the oracle tape (instead of ...
1
vote
0answers
19 views
Is there an analogue of Kolmogorov Complexity for Strongly Normalizing Languages?
The definition of Kolmogorov Complexity relies upon the definition of Turing Complete description languages. Famously, Kolmogorov Complexity is uncomputable and akin to the halting problem. I have two ...
2
votes
2answers
44 views
What would a Turing Machine that used functions as input/output and performed transformations on the function be able to do?
Before I even begin my question, I'm going to start off with a couple disclaimers:
Disclaimer 1: I'm not sure this really belongs on Mathematics, but I'll go for it anyways since it's the closest SE ...
1
vote
1answer
109 views
Is it possible to construct a model of oracle Turing machines that correspond to $\omega_n^\text{CK}$, where $n$ is greater than $1$?
I have found the following quotes. Quote $1$ ( source ):
In computability theory, Turing Machines+BB oracles correspond to the same ordinal as ordinary Turing Machines ($\omega_1^\text{CK}$). In ...
0
votes
0answers
30 views
Turing's argument that computable sequences are enumerable
In Turing's paper from 1936, he shows how the following counter-argument is a fallacy:
If the computable sequences are enumerable, let $\alpha_n$ be the $n$-th computable sequence, and let $\phi_n(...
1
vote
2answers
99 views
Is it possible to assume the existence of “Dominating Turing Machines”?
Consider three-tape (tape $1$ for the input, tape $2$ for the computation, tape $3$ for the output) two-symbol (blank symbol and non-blank symbol) Turing machines.
Let $F(x, y)$ denote the minimal ...
3
votes
1answer
64 views
Algorithm to decide the universality / functional completeness of a set of logic gates?
Given a set of logic gates $G$, let $F_G$ denote the set of all formulas composed of gates from $G$. We say that $G$ is "universal for computation" or "functionally complete" if it forms a basis for ...
5
votes
1answer
80 views
How many variables do you need to be complete for $\Sigma^0_n$?
The arithmetic hierarchy is a structure on sentences in first order logic. It has a particular relationship with computability, due to Post’s Theorem.
In most discussions of the arithmetic hierarchy, ...
1
vote
1answer
66 views
Turing Machine that orders the alphabet/characters of the entered string based on the frequency of each symbol
Give the following problem:
Design a Turing Machine such that given string from the alphabet $\{a, b, c, d\}$, produces on the tape a combination of the string "abcd" in which each symbol occupies ...
2
votes
0answers
173 views
When does the busy beaver function surpass TREE(n)? [closed]
Since TREE is a computable function the BB function grows faster than it, but TREE seems to grow much more quickly early on, so when does Busy Beaver surpass it?
0
votes
0answers
30 views
Representation of Turing machine to prove Cook-Levin theorem
How would one construct function which is representation of some Turing machine (which is in one state at each step) which can be used to prove the Cook-Levin theorem?
It is written on Wikipedia in ...
-1
votes
1answer
76 views
Why does Turing-computing (being an inconsistent formalism) has undecidable problems? [closed]
I'd like to apply Church-Turing thesis to Kleene-Rosser paradox:
Since untyped lambda-calculus is an inconsistent formalism
AND
Turing machines are equal in decisive power to lambda-calculus
SO
We ...
