Questions about Turing machines, a theoretical model of mechanical computation capable of simulating any computer program.

learn more… | top users | synonyms

0
votes
1answer
28 views

Is a partial function Turing-computable?

From my understanding for a function to be considered Turing-computable the Turing machine which computes it must terminate for all inputs (according to this http://planetmath.org/turingcomputable and ...
-2
votes
0answers
12 views

Proving that a language is not co-RE but not RE [duplicate]

Let $A = \{ (M,N,w) \mid M\text{ and }N \text{ are TMs and exactly one of them accepts }w \}$. So, in particular, if $(M,N,w)\in A$ then $L(M)\neq L(N)$. Here is how I have shown that $A$ and its ...
-2
votes
0answers
13 views

Reducing turing machines [duplicate]

Can anyone help me with this problem: Reduce (and prove it's a reduction) ...
0
votes
1answer
44 views

Proving a language is not Turing-recognizable by reduction

I'm having a really hard time understanding some of these concepts. I've read them over from several different sources and still can't reach the a-ha moment. I need to prove a language L is not ...
1
vote
1answer
80 views

Is the following statement about turing machines true?

Here's the statement: Take a set of finite inputs from some alphabet. If for any two turing machines: All inputs in the set produce the same output for both machines In both machines, ...
1
vote
2answers
46 views

Is it true, If $A$ is turing recognizable and $A \leq_m\bar{A}$ then $A$ is recursive?

If $A$ is turing recognizable and $A \leq_m\bar{A}$ then $A$ is recursive? If it is true how to prove it? Update It is my attempt, If $A$ is turing recognizable (r.e.) and $\bar{A}$ is r.e. then ...
1
vote
3answers
109 views

Examples of processes / problems that cannot be tackled by Turing Machines

I know that there are problems that cannot be solved by any algorithm, such as the Halting problem. I also know that some processes cannot be even adequately approximated by any Turing Machine ...
0
votes
1answer
130 views

PDA with N-Stacks comparison with Turing Machines [duplicate]

Is it possible to compare PDA having N-Stacks with Turning Machines. Are they equally powerful in this situation? It's been told that PDA with 2-Stacks is equally powerful to Turning Machine. But ...
-1
votes
0answers
33 views

Can Push Down Automaton (PDA) with n-stacks be equally powerful to a Turing machine ? [duplicate]

Can Push Down Automaton (PDA) with n-stacks be equally powerful to a Turing machine while dealing Context Free Languages (CFG)?
0
votes
0answers
63 views

Is the language of Turing Machines that halt on every input recognizable?

I am trying to reduce the complement of the HALTING problem (WLOG, the complement of the HALTING problem is the language of TMs that loop on some string w)to this language in order to show that it is ...
0
votes
0answers
31 views

Designing a turing machine to determine if there is path from two vertices in a directed graph or not

I'm self studying automata and I'm in chapter 7 of Sipser book. I want to design a diagram for a Turing machine that shows if there is path from s to t in a directed graph. My tape is like this: ...
0
votes
1answer
32 views

How to design a Turing Enumerator which either ends with 011 or is of odd length? [closed]

This question was asked by my professor in optional brain teaser section, I have tried to solve it for last 48 hours, I am not able to construct a deterministic Turing Machine, Can someone provide ...
1
vote
0answers
27 views

Decidable non time constructible function

Can anyone help me find an example of a function $f:\mathbb{N}\rightarrow\mathbb{N}$ which satisfies $\forall n\in\mathbb{N}: f(n)\ge n$ and is decidable, i.e. there exists some Turing machine $M_f$ ...
4
votes
2answers
1k views

What is 'halting'?

I've read a definition that says that "co-semi-decideable' means that a TM is halting on all inputs NOT in the language. I've heard the word come up a lot, and I've so far assumed that halting just ...
3
votes
1answer
81 views

I/O in Theory of Computation

I posted a question "Arbitrary Programs that halt" some days ago and now i think my doubt is a lot more clear. I concluded that in any arbitrary program that halts, control flow operations, ...
0
votes
2answers
46 views

Turing Machines: Arbitrary alphabet equivalence with binary alphabet

Think of an $n$-ary alphabet as $\{0, 1, ..., n-1, n\}$. For example, a binary alphabet is $\{0, 1\}$. Do Turing Machines with binary alphabets decide the same set of languages as Turing Machines ...
3
votes
1answer
73 views

Arbitrary Programs that Halt

I've been learning about Theory of Computation lately, and i'm trying to link general programming with the Theory of Computation. I thought of considering any arbitrary program that halts, as an ...
0
votes
1answer
50 views

Proving that it's decidable whether a TM ever moves on the blank input

I'm trying to understand how to prove a language is decidable, semi-decidable, co-semi-decidable, or none of the above. I've got the problem: $$A_{\mathrm{right}} = \{ \left< M\right> | M ...
2
votes
2answers
38 views

will this be decidable or partially decidable?

$A=\{\langle M \rangle \mid M \text{ is a turing machine and }|L(M)|\geq3\}$ Since Recursive enumerable languages are turing enumerable, so listing of all strings of the language in finite time is ...
3
votes
1answer
51 views

Are there criteria that will make: $A \subseteq B$, $A$ unrecognizable imply $B$ unrecognizable?

Let $A \subseteq B$, and A is unrecognizable. I know in general that doesn't mean B is unrecognizable. However, are there some limitations we could put on A and B that would make it true? The only ...
0
votes
0answers
23 views

Can we write algorithms without conditional statements? [duplicate]

Regarding turing completeness, i read that for a language/machine to be turing complete it is required that it has some sort of conditional. Consider the factorial problem, we would typically define ...
1
vote
1answer
60 views

Is $T=\{\langle M\rangle \mid |L(M)| =1 \text{ or } |L(M)| >2\}$ recognizable?

$$T=\{\langle M\rangle \mid |L(M)| =1 \text{ or } |L(M)| >2\}$$ I started with Rice's theorem (come up with an example where $|L(M)| = 2$) to see that $T$ was undecidable. Then I figured out ...
5
votes
4answers
835 views

Can we write algorithms without conditional statements?

Regarding turing completeness, i read that for a language/machine to be turing complete it is required that it has some sort of conditional. Consider the factorial problem, we would typically define ...
2
votes
1answer
22 views

Looking for an example of proving space upper bounds for computing functions on a DTM

Like think of the function $f\colon \{ 0,1\}^* \rightarrow \{0,1\}^*$ which maps a binary string string $x$ to say a string of $0$s of length $\vert x \vert ^2$ whre $\vert x \vert$ is the length of ...
0
votes
1answer
20 views

How to prove computational completeness of a variant of P system

I have read a lot of books on membrane computing (P system), of which the computational completeness of several variants are already under investigation. My goal is to design my own variant and prove ...
5
votes
1answer
82 views

Combinational Logic Circuits and Theory of Computation

I'm trying to link Combinational Logic Circuits ( computers based on logical gates only ) with everything i have learned recently in Theory of Computation. I was thinking whether combinational ...
0
votes
0answers
41 views

Are all Turing machines recognizable? [duplicate]

Is the language of the set of descriptions of all Turing machines recognizable? I'm thinking not, but I can't quite define why. A language is Turing-recognizable if some Turing machine recognizes ...
2
votes
1answer
129 views

Language consisting of all Turing machine encodings [closed]

$A=${$ ⟨M⟩$:$M$ $is$ $a$ $Turing$ $Machine$ } What can be said about $A$ ? Specifically, is $A$ decidable,regular,CFL,CSL? I would say $A$ is decidable since we can write an algorithm to check ...
2
votes
2answers
21 views

$3EQ \leq _P 2EQ$

Let: $2EQ$ - The language of all binary ($\mathbb{Z}_2$) equation sets that have a solution in $\mathbb{Z}_2$, where each multiplication is of at most two $x_i,\, x_j$. Meaning a set of equations of ...
2
votes
2answers
71 views

Where can I find a high quality copy of Turing's On Computable Numbers?

Currently, I'm reading a photocopied version of Turing's famous article On Computable Numbers, With an Application to the Entscheidungsproblem. This is the best photocopy of his paper that I can ...
1
vote
1answer
32 views

turing machine decidability proof [closed]

An exercise problem once again has me stumped on a Turing Machine decidability proof. We are given an alphabet with the strings 0 through 9. Along with this, we have x as the infinite string of all ...
0
votes
1answer
38 views

NXOR for 2 inputs on a turing machine, in P?

Question: L is the language of $\langle M,x,y\rangle$ s.t TM $M$ accepts both inputs $x$ and $y$ or doesn't accept either. Prove that given some $M$, finding 2 inputs $x$ and $y$ s.t. $\langle ...
0
votes
1answer
58 views

Turing Machine notation

I'm a bit confused on some of the notation being used for turing machines in one of our exercises in class. The question gives us a string $\alpha \in \{0,1\}$* and the function ...
2
votes
0answers
34 views

What are the fundamental principles/algorithms on the process of equation solving?

I have seen a lot of solvers that are capable of, for example, getting an equation such as x ^ 2 + x = 12 and finding x = [3, -4]. I know some of them are implemented by hardcoding special cases. For ...
0
votes
2answers
68 views

Difference between Turing machine end state and halt

Is there a difference between the end state of a Turing machine and the halt state? Especially, for example the Busy Beaver 3. It is said that it is with 3 states but there is also a halt. Is the end ...
1
vote
0answers
23 views

Constructing a TM from empty string

Hey I want to construct a deterministic Turing Machine, which out of an empty string tapes six consecutive 1s when halt. I have a question, is it possible to create such without transitions from final ...
0
votes
0answers
49 views

Turing machine from empty string: verification and suggestions

So I must create a Turing machine which records from empty tape six consecutive 1s. I am allowed to use only 3 states. $z_2$ is the final state. Furthermore, it should be deterministic. Here is my ...
0
votes
1answer
58 views

closure property on languages

The above image, taken from planetmath.org, describes the closure property on REG (regular), DCFL (deterministic context-free), CFL (context-free), CSL (context-sensitive), RC (recursive), RE ...
1
vote
1answer
61 views

Does stay put TM recognizes same languages as standard TM

I am reading this text book and it says that stay put turing machine recognizes the same languages as regular turing machine by just adding transition functions (without adding any new states or ...
1
vote
0answers
52 views

Models of Computation and What they can model [closed]

Some days ago i've discovered that in most of what we call "models of computation ", we can possibly model tasks other than computation itself . For instance, in lambda calculus we can model control ...
0
votes
2answers
41 views

Constructing Turing machines

I get the main ideas of Turing machines. But I can't construct a Turing machine to solve a given question. The question I'm trying to solve is "Construct a Turing machine that recognises the set of ...
7
votes
2answers
62 views

Computability of equality to zero for a simple language

Suppose we have a tree in which leaves are labeled with a set of numbers $L$, and internal nodes with a set of operations $O$. In particular $L$ can be $\mathbb{N}, \mathbb{Z}$ or $\mathbb{Q}$, and ...
3
votes
1answer
24 views

What does $\Sigma^0_2$-hard and $\Pi^0_2$-hard for a TM's Acceptance Problem mean?

I'm reading about a Turing Machine $M$ and it says the problem of deciding whether M accepts a string is "$\Sigma^0_2$-hard and $\Pi^0_2$-hard". I haven't seen this kind of notation before and ...
2
votes
1answer
109 views

Using Generalized Rice's Theorem to Prove Decidability

I have a Turing Machine M with a binary alphabet {1,2} that accepts a language L(M) that has infinitely many strings that start with 1 and finitely many strings that start with 2. I'm trying to ...
2
votes
1answer
221 views

Proving Infinite Turing Machine Language (with finite subset) is Recursively Enumerable

I'm trying to answer this question: Let $S$ be the strings $\langle P \rangle$ accepted by the Turing Machine $P$ with input alphabet $\{a,b\}$, where $P$ accepts an infinite number of strings ...
1
vote
1answer
20 views

Space penalties for the simulation of a non-deterministic Turing machine by a single-tape deterministic Turing machine

If I have some non-deterministic Turing machine $NDTM$ running some process $Q$ and I wish to simulate the same process $Q$ with a deterministic single-tape Turing machine $DTM$, there will of course ...
5
votes
2answers
482 views

Are two non-Turing-recognizable languages closed under union?

If I have two languages that aren't Turing-recognizable, is the union between them always not T-recognizable? Why?
1
vote
1answer
29 views

Are all languages generate by Turing machines countable?

Are all languages generate by Turing machines countable? I know that the set of all TMs are countable, but what about the languages that they generate?
1
vote
3answers
87 views

Turing Machine That Accepts Machines With Undecidable Languages

So I'm reviewing my Computability notes for my final, and I understand how reduction arguments work, but I'm having trouble framing one for the following Turing machine: Undecidable TM = { ⟨M⟩ | L(M) ...
-2
votes
1answer
31 views

How can I construct a Turing Machine that accepts encoding of another Turing Machine? [closed]

How can I construct a Turing Machine that accepts the language L = <'M'> which is an encoding of a Turing Machine M?