This tag is suited for questions involving Turing machines. Not to be confused with finite state machines and finite automata.

learn more… | top users | synonyms

0
votes
0answers
10 views

NDTM vs DTM running time of a program

I've found the following statement: If a program $P$ for Non Deterministic Turing Machine solves a decision problem in time limited by a polynomial $p(S)$, where $S$-size of input, then it can be run ...
0
votes
0answers
25 views

Turing machine notation question.

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 α ϵ {0,1}* and the function int(α) that changes a binary ...
1
vote
1answer
23 views

Turing machine recognizing language $L=\{a^ib^{i-j}c^j|i>j\ge1\}$

I am having some trouble with designing a Turing machine that recognizes the language: $L=\{a^ib^{i-j}c^j\big|i>j\ge1\}$ For example, word accepted by TM: $w=aaaaabbccc$ To be more precise, I ...
0
votes
1answer
29 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
2answers
53 views

turing machine with exactly 42 states / state that is visited at least 42 times

I am trying to solve the following problems: Proof wether the following problems are decidable/undecidable: Given turing machine M: Does M have exactly 42 states? Given turing machine M: Does M ...
3
votes
0answers
17 views

Show that minimal CFG is undecidable (Sipser 5.36)

Question: Say that a CFG (context-free grammar) is minimal if none of its rules can be removed without changing the language generated. Let $MIN_{\text{CFG}}$ = $\{\, \langle G \rangle$ | $G$ is a ...
3
votes
1answer
58 views

Using Extended Rice's Theorem to Prove Decidability

I have a Turing Machine M. Let L be the set of all strings representing the encoding of M that has input alphabet {1,2}, where M accepts infinitely many strings that start with 1 and finitely many ...
1
vote
1answer
39 views

two way infinite turing machine?

A Single tape turing machine is generally unbounded to right and starts from left. Read/write head moves to right from left after consuming a symbol. But what if we make left side unbounded too and ...
2
votes
1answer
26 views

Can a halting turing machine write any combination on a tape before halting?

Assume, a halting turing machine uses $n$ items of the tape. Can it write every possible combination on this $n$ items before halting ? We start with a blank tape. Example $n=2$ , alphabet $0,1$ ...
0
votes
0answers
14 views

program which it's power is equal to LBA

Can anyone give an opinion about this matter: what is the smallest program which it's power is equal to LBA Turing machine(Linear bounded automata are acceptors for the class of context-sensitive ...
0
votes
1answer
37 views

Help understanding a 'reversing a string' Turing Machine

I am having a bit of a confusion understanding some transitions in a Turing Machine. Its an example from Introduction to Languages and the Theory of Computation by John C. Martin. I've attached the ...
0
votes
1answer
35 views

How to design a turing machine that recognizes any language?

here I have a problem. Design a turing machine that recognizes the language of all strings of even length over alphabet {a, b}. soln: Let turing machine is $Tm =(Q, \Sigma, \Gamma, \delta, q_0 , ...
1
vote
0answers
40 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) ...
0
votes
0answers
21 views

Turing's Corrections on his 1936 paper On computable Numbers

On Turing's proof of the "Lemma 1" (If $\ S_{1}\,$ appears on the tape in some complete configuration of$\ M\,$,then$\ Un(M)\,$is provable) He states that we are unable to deduce$\ F^{n+1} \to ...
0
votes
0answers
23 views

is it in fact impossible to construct a machine which can know if a macine ever prints a character?

In $\S\ 8$ of his paper "On computable numbers, with an application to the Entscheidungsproblem" Turing uses his proof that $\mathfrak{D}$ (a machine which given the S.D. of another machine ...
0
votes
0answers
81 views

could a machine $\mathfrak{D^+}$ be made to produce $\beta$ so the diagonal argument could be used on computable numbers?

I was reading Turing's paper "On computable numbers, with an application to the Entscheidungsproblem" and while reading $\S\ 8$ (his proof that computable numbers are enumerable) and his proof that ...
0
votes
0answers
23 views

Designing a turing Machine belonging to a language

Im trying to learn the concept of turing machines.I have understood the basic stuff like its a simple mathematical model of a computer and its parts.Now im asked to create a turing machine. ...
0
votes
1answer
35 views

Is my Turing Machine (Transition Function) correct for finding if a string is of even or odd length?

I've been asked to create a formal Turing Machine (by means of a transition function) to which takes a string $a^n \in$ {a}* and decides whether it is an even or odd length. What I have made is the ...
0
votes
0answers
20 views

Show that L4 is decidable (i.e., recursive), by describing a Turing machine that decides L4.

L4 = {<M, w> | M is a turing machine, w is a string, and M never moves it's head left on input w} I know that M is allowed to move to the head to the left ...
1
vote
1answer
39 views

Is universality decidable?

Is there a turing machine which can take any other TM T as input and decide whether T is a universal turing machine?
0
votes
1answer
17 views

Multitape Turing machine with multiple non-blank tapes

A multitape Turing machine is defined to have input only appear on one tape, with the rest of the tapes blank. Are there any formulations of a Turing machine that allow other tapes to be not blank? ...
0
votes
1answer
60 views

Relationship between the Turing Machine and RAM Models

Could you tell me which is the relationship between the Turing Machine and RAM Models??
0
votes
1answer
34 views

Recursively enumerable sets: the halting set

Wikipedia on the Halting Problem: The conventional representation of decision problems is the set of objects possessing the property in question. The halting set $K := \{ (i, x) ~|~ \textrm{program ...
1
vote
0answers
23 views

Dual Turing Machine Simulation

(1) Define a Turing Machine that simulates a Dual Turing Machine (DTM)?. A dual Turing Machine is defined as a Turing Machine with 2 heads and 2 tapes. At every step, the DTM can read from either ...
0
votes
0answers
11 views

Turing machine that modifies each cell that contains a certain input one time at most

If I have a single tape turing machine running on some input $x$, where it modifies each part of the tape with $x$ one time at most...would the TM be decidable? Any advice or guidance appreciated; ...
2
votes
1answer
60 views

Zermelo–Fraenkel Set Theory

So I'll try keeping this real short and simple. Assume that language $L$ is defined as $\{ x\in \{0,1\}^* \}$ (finite binary strings) such that $x$ encodes a proof in ZFC that 4 is a prime number. I ...
0
votes
1answer
36 views

Simple Turing Machine

Having a bit of trouble designing a turing-machine which recognizes the following language. The alphabet is $\Sigma$ = {a,b,c}. $$ L_2 = \{wcw^R | w \epsilon \{a,b\}^*\} $$ The part which messes ...
0
votes
1answer
24 views

cubic integral roots

I am trying to find the integral roots (if they exist) of the following polynomial. Additionally, it would be helpful if someone could explain an algorithmic approach to solving this. $$ f(x) = 2x^3 ...
0
votes
2answers
91 views

If all infinite r.e. languages have an infinite recursive subset, then do co-r.e. languages not have such subsets?

If all infinite r.e. languages have an infinite recursive subset, then can we take it to be true that co-r.e. languages do not have such subsets by complemence?
2
votes
1answer
20 views

Turing machine that goes left on first symbol

I have a turing machine with transitions given by the following table I'm inputting the string aaaa. So if I look at the first symbol "a" in state A, it says to replace it with an X, go into state ...
2
votes
0answers
46 views

How to find the shortest path of a graph in a turing machine

I'm reading about Turing machine and I saw some examples as: Let $M_{1}$ a Turing Machine and the language $B = \{w\#w \vert w \in \{0,1\}^{*}\}$, We want $M_{1}$ to accept if its input is a member of ...
0
votes
0answers
20 views

If we create a partition of $E_{TM}$ by listing its elements, are the subsets undecidable?

Consider the set $E_{TM} = \{ <M>$ | M is a TM such that $L(M) = \emptyset\}$ The set of all Turing Machines in countable. Thus $E_{TM}$ is countable. Suppose we list all elements of $E_{TM}$ ...
0
votes
0answers
14 views

Showing that $f(K) = {f(a) : a ∈ K}$ is recursively enumerable

Today we went over things that are recursively enumerable, but I cant seem to grasp how to prove the equation $$f(K) = {f(a) : a ∈ K} $$ is recursively enumerable. I can prove that equations are ...
3
votes
0answers
93 views

Whats the connection between Turing machine and First order logic?

Today in my Computing class i came across the theorem which states that., If language $L$ and $\Sigma^*\setminus L$ are recursively enumerable then L is recursive (total turing machine). Which looks ...
3
votes
1answer
42 views

Is there a recursive injective and surjective function f:N→PRF?

It is well known and easy to see that it is possible to effectively number Turing Machine codes. That is, there is an injective and surjective recursive mapping $g:\mathbb N\to {\rm TM}$: each Turing ...
1
vote
0answers
30 views

BusyBeaver growth: “simple” proof

I just try to prove that $BB(n)$ (BusyBeaver-Function) grows faster than any other computable function. Maybe someone can check the proof? $f(n)$ is a computable function which grows to infinity: ...
3
votes
1answer
142 views

Challenge on Some Language and PDA

Suppose We have Some language as follows: $L_1=\{w^* | w=x \text{ and } x \in \Sigma^*\}$ $L_2=\{ww^R ww^R | w \in ( \Sigma + \Sigma)^*\}$ $L_3=\{w | w=xy, x,y \in \Sigma^*, y \text{ is a ...
1
vote
7answers
144 views

Text books on computability

I collected the following "top eight" text books on computability (in alphabetical order): Boolos et al., Computability and Logic Cooper, Computability Theory Davis, Computability and unsolvability ...
2
votes
0answers
84 views

Challenge on Some Definition on Formal Language & Recursive & Automata

We know set A is countable if A is finite or in a one-to-one mapping to natural numbers. Suppose $\Sigma$ be an arbitrary finite alphabet. I summarize my inference: a) Each arbitrary Language on ...
1
vote
1answer
29 views

Gathering nonconsecutive 1's by a Turing machine

S. Barry Cooper comments his output convention for $\mathbb{N}\rightarrow\mathbb{N}$ Turing machines like this: Outputting $n$ as $n$ possibly nonconsecutive $1$'s is very natural. [...] We can ...
0
votes
1answer
20 views

Non-Deterministic Polynomial Time Algorithm

My understanding is that for problems where there are an exponential number of possible solutions, a non-deterministic turing machine (NTM) is able to solve it in polynomial time because an NTM can ...
0
votes
2answers
102 views

Input and output of a Turing machine

For some machine models of computation there is no question what their input and output is: it's just the contents of some specific "cells", e.g. on a "tape" isomorphic to $\mathbb{N}$. Consider for ...
0
votes
0answers
11 views

Is the set $L =\{ M_ i: M_i$ accepts only one string$\}_{i=1}$ an recursive enumarable set?

I am having trouble with this question "Is the set L = {i such that M_ i accepts only one string} an recursive enumarable set ?" My answear is "No, because we can reduce this set to The K set K={i ...
1
vote
1answer
31 views

Show that whether or not an arbitrary Turing machine ever executes a particular one of its instructions is unsolvable

Show that whether or not an arbitrary Turing machine ever executes a particular one of its instructions is unsolvable. (This is the same as the problem of detecting unreachable code in a program.)
0
votes
1answer
30 views

Turing machine algorithm and Natural number

Let T be a deterministic Turing machine and let A be a set of all algorithms which is running on T. I know that there is an algorithm F which can transform an Algorithm $X$ into a Natural number ...
0
votes
1answer
96 views

Turing Machine Problem

We know, A Turing machine is a hypothetical device that manipulates symbols on a strip of tape according to a table of rules I Draw a TM for input $x=(0+1)^*$ i want to implement ...
2
votes
1answer
39 views

$L=${$a^nb^nc^n : n \geq 0 $} CFG Recognizing

Suppose $L=${$a^nb^nc^n : n \geq 0 $} and I. $h(L), h(a)=a, h(b)=bb, h(c)=b$ II. $L^R$ III. $L^*$ IV. $h(L), h(a)=a, h(b)=bb, h(c)=a$ Why just I is a CFG and other is not? anyone can help me to ...
1
vote
0answers
41 views

Proof that Finite Turing Machine is reducible to Regular Turing Machine

I know that Finite Turing Machine and Regular Turing Machine are undecidable through Rice's theorem, but I may find a reduction among them? Finite TM = {< M > | L(M) is finite on {a}} Regular TM ...
-1
votes
1answer
59 views

PDA and Some language Grammar inference

L1={$w^* $| w=x and $ x \in \Sigma^*$} L2={$ww^R ww^R $| $ w \in ( \Sigma + \Sigma)^*$} L3={$w | w=xy, x,y \in \Sigma^*$, y is a substring of x} a) there is a PDA(push down automata) that accept ...
0
votes
1answer
40 views

Pushdown Automata and Challenge in Grammar

I read one old-midterm exam on Automata. consider: the language that accepted by above pushdown automata is not generated by which of the following grammar? 1) S->aBaa|a$\epsilon$ ...