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

learn more… | top users | synonyms

0
votes
1answer
20 views

How does augmenting linear bounded automata tape alphabets increase memory?

A linear bounded automaton is a Turing machine that is restricted by memory. How would augmenting the tape alphabet of a linear bounded automaton increase its memory? While the memory that the ...
6
votes
4answers
108 views

Undecidable problems limit physical theories

Does the existence of undecidable problems immediately imply the non-predictability of physical systems? Let us consider the halting problem, first we construct a physical UTM, say using the usual ...
-2
votes
0answers
19 views

How do we explain this in Dovetailing [closed]

A=Turing Machines that accept only 1 string. A= Not recursively enumerable. A'= Not recursively enumerable. Question is how can we prove it. Explanation if other than dovetailing concept would be ...
3
votes
1answer
386 views

Good introduction to Turing's work and complexity theory?

I'm currently an undergrad whose been amazed by what Turing has done for the world. I know there are plenty of other amazing individuals, but Turing's work specifically has always sounded the most ...
2
votes
1answer
62 views

Power of variants of Turing machines

I'm having trouble with this problem as I haven't discovered a good way to determine the power of a Turing machine. I was under the impression that if a Turing machine can perform the same actions ...
2
votes
1answer
37 views

What is a standard way to construct a turing machine for any function to compute

I am new to turing machines, I am having problems with mapping a function to a turing maching that computes that particular function. for example: f(x) = 2x + 3 n>= 0 MIN(x,y) leaves the smallest ...
-1
votes
0answers
30 views

Statments about recursive and recursively enumerable languages [closed]

I need help with proof of the following statements: If L1, L2 are recursive and L3=L1-L2 then L3 is also recursive. I know that there is TM1 which accept\reject any word of L1 and there is TM2 ...
1
vote
1answer
42 views

m-functions in Turing's paper “On Computable Numbers and applications…”

I was reading Alan Turing's paper "On Computable Numbers with an Application to the Entscheidungsproblem". I was reading well until I encountered "4. Abbreviated Tables", page 235-236, where Turing ...
0
votes
0answers
25 views

How many valid and unique Turing machines are there with restricted states and characters

This is based off of my question here, where I was helped to find the number of Turing machines with restricted states and characters which is $(3(c+1)(n+2))^{(c+1)n}$. Now I'm wondering how many of ...
1
vote
1answer
31 views

Infinite Memory

It seems to me that any problem whose solution requires finite memory can be emulated on a Finite State Machine . This would make those problems that can't be solved by a Finite State Machine to ...
0
votes
1answer
38 views

How many Turing machines are there with $c$ characters and $n$ states?

By $c$ character I mean the numbers $0,\dots,c-1$ and the blank symbol $b$, and by $n$ states I mean $n$ non-accepting states, reject and accept. We can assume every $n$-state Turing machine has ...
0
votes
1answer
37 views

Prove Undecidability: TM M enters each of its states on Input W?

Consider the following problem: given a Turing Machine $M$ and an input string $w$, does $M$ enter each of its states during its computation on input $w$? How to prove that the problem is ...
0
votes
2answers
56 views

Identifying and describing the language accepted by a Turing machine [closed]

Given a Turing machine, how can I identify the language it accepts and write a set notation for L(M)?
0
votes
2answers
66 views

simulation of PDA with turing machine

How to simulate a non-deterministic PDA with a turing machine?
1
vote
1answer
21 views

Proving a language to be Recursively Enumerable?

I know to prove a language to be Recursively Enumerable, it is ideal to represent a Turing machine for it. Let L be set of strings which have alphabet {u,d,l,r}, where u is up 1, d is down 1, etc. L ...
8
votes
8answers
2k views

Why does a Turing machine recognise exactly one language?

I am trying to understand the existence of non-recognisable languages. To get this, I need to know why a Turing machine recognises only one language, not multiple. Why is this?
0
votes
1answer
46 views

Infinite u decidable languages

I am trying to see if infinite languages are always decidable. I believe it is not always decidable because there will not be a maximum length of string for the Turing machine to halt. Am I on the ...
0
votes
2answers
83 views

How is the computational power of a human brain comparing to a turing machine?

This seems related to these questions at a glance: What are some problems which are easily solved by human brain but which would take more time computers? What would show a human mind is/is not ...
0
votes
1answer
47 views

Turing Machine construction

How should I go about building a Turing machine for the following language: L = { $ a^ib^j ∈ (a,b)^* | i ≤ j ≤ 2i $ } I know how to construct a Turing machine for { $ a^nb^nc^n | n ∈ N $ } but ...
1
vote
2answers
120 views

Doubts about infinite language decided by a turing machine

Assume you have an infinite language $L$ over alphabet $\Sigma=\{a,b\}$ For example, $L=\{ax \mid x \in \Sigma^*\}$ Can a Turing Machine, $M$ decide this language? (Generalizing, are all the ...
2
votes
1answer
37 views

Is multiprocessing possible on a turing machine?

I recently created a parallel implementation of the Merge Sort, in which the sorting of several groups was accomplished by different processes, and was wondering if this was theoretically possible on ...
2
votes
1answer
93 views

$P \neq NP$ and determinism

Suppose $P \neq NP$. Does it imply that there exists some superpolynomial time bound, such that any $NP$-complete problem, like SAT, can be used to simulate an arbitrary deterministc Turing Machine ...
3
votes
3answers
96 views

Splicing squares on a Turing Machine finite tape

Trying to explain a problem, I thought of a variant of Turing Machines. It is unlikely to be new, but I do not recall ever seing it before, and I wonder whether it has been used or has a name. The ...
1
vote
3answers
102 views

Understanding definition of NP

In my lecture notes, the definition of the class NP is given as: A language $L$ is in the class NP, if there exists a turing machine $M$ and polynomials $T$ and $p$ such that: For every input $x$, ...
1
vote
3answers
141 views

How to replace one symbol with two on Turing machine's tape

I want to implement following algorithm on Turing machine: rewrite binary numbers to their unary counterparts. For example: 101 will be rewritten to a string of 5 consecutive bars (wikipedia) ...
1
vote
2answers
62 views

Proving the set of finite languages is countable without using the union of countable sets

The list of finite languages over a finite alphabet is countable. I could prove it by saying that the list of languages of size 1 is countable, the language of size 2 is countable, and so on. Then I ...
4
votes
1answer
298 views

Why is automated theorem proving impossible?

As far I know, in general case there is no Turing machine which could get any theorem on its input and produce its proof on its output. Why is it so?
0
votes
1answer
21 views

Transitions needed for dividing two fixed integers

Let $Q$ be the set of states of the Turing Machine, $\Sigma$ be the alphabet, and $\{L,R,S\}$ be the left shift, right shift, and stay respectively. A transition is an element of $Q \times \Sigma ...
1
vote
1answer
66 views

How exactly does a two stack pushdown automaton work?

I have to explain how a 2-PDA works and then write a program (in Delphi) which simulates a 2-PDA step by step for the language $L = \{w\$w\ |\ w ∈ \{0,1\}^n\ with\ n>0\}$. So far, so good. Now I ...
3
votes
1answer
35 views

Can I encode a graph in a unary alphabet

For a graph $G=(V,E)$, I build an adjacency matrix and encode it into binary, clearly. Now, imagine the alphabet I am given is $\Sigma=\{1\}$, is there a way for me to encode any graph instance with ...
0
votes
2answers
362 views

Turing Machine that computes maximum steps of halting machines

Suppose that $TM_{halting}$ is the set of machines that halt. Given a number of states $m$ and a length $n$ of the input, let $f(m,n)$ be the maximum number of steps a machine with $m$ states in ...
2
votes
1answer
80 views

Is deciding whether the language of a TM contains all strings of length 4 computable?

I was going through some Halting Problem reduction and I found the following problem: Given a semi-decider TM $M$, does the language $L(M)$ contain all strings of exactly length $4$? The ...
6
votes
1answer
80 views

How can a universal Turing machine simulate “bigger” ones?

I'm trying to find the answers of two questions about the Universal Turing machine. How can the Universal Turing machine simulate a Turing machine if the one that is being simulated has a bigger ...
2
votes
0answers
35 views

Why would $NP^ {SAT} \subseteq P^{SAT[O(\text{log }n)]}$ imply that $PH \subseteq P^{SAT[O(\text{log }n)]} $

I was reading the following paper by Jim Kadin, "$P^{NP[O(\text{log } n)]}$ and sparse Turing complete sets for NP" The main result is that if there is a sparse set $S \in NP$ such that $coNP ...
0
votes
1answer
43 views

Turing Machines and Algorithm for Language Acceptance

Is there an algorithm to decide if any two Turing machines accept the same language? I can't find a definite answer to this. My guess is that there isn't, because then we would be able to decide if ...
-1
votes
1answer
50 views

NDTM for Graph Clique Problem in poly-time

I am having a doubt. This is my NDTM algorithm: GCP(G, k): generate a list with k distinct nodes from graph G generate an adjacency matrix, fill it with 1 if an edge exist, 0 otherwise check if ...
0
votes
1answer
38 views

How does a turing machine with doubly infinite tape simulate a normal-taped turing machine?

The intuition is that on any input, we can write a symbol like $\#$ on the left that tells the machine to not move past this symbol. However, I'm running into problems trying to show this using the ...
2
votes
2answers
80 views

Non-erasing Turing machines and loss of generality

A non-erasing Turing machine is one that cannot replace a symbol with a blank unless the symbol under the read head is a blank. I'm trying to understand whether there is loss of generality because of ...
3
votes
1answer
34 views

Non-deterministic vs Deterministic turing machine to solve graph colouring

For graph coloring decision problem I mean the following: given a undirected graph, $G$, we have $GCDP(G, n)$. This returns yes instance is given if it we can color the graph with n different colors. ...
0
votes
0answers
16 views

Forward jump turing machine and r.e languages [duplicate]

I was going through some exercises I found online and I am really stuck at this problem: Consider Turing Machines with the following restriction: they are only allowed forward jumps, i.e. if ...
2
votes
3answers
70 views

Turing machine for unary encoded quadratic numbers

I want to design a turing machine that accepts strings of the form $0^{n^2}$ where $n \geq 1$ and I want to give an implementation description for this. So I am thinking that the algorithm can go ...
-2
votes
1answer
23 views

Quadratic lower bound for deciding the set of palindromes

How to prove a single tape Turing machine needs at least n squared time to decide palindrome? This is an exercise from the "computational complexity - a modern approach" book.
0
votes
1answer
25 views

How do I manage flow control with no ELSE statement? (on Turing machine)

I have been given the problem of writing a turing machine with the commands: if, while, whileNot, read X, write X, goLeft, goRight, HALT The problem was simply ...
1
vote
1answer
40 views

If A is decidable and B is decidable, then A is Turing Reducible to B

The statement seems intuitively true but is it? If so, how can I prove this?
0
votes
0answers
29 views

P-time reduction A < B where B has no no-instance

I had a question to prove whether a reduction can exist $A < B$, if B has no no instances and one yes instance. I am not sure if this is too trivial. Let $A \in P$ and $Y$ be the only yes-instance ...
2
votes
0answers
70 views

A complete catalog of 2-state Turing machines?

For educational purposes, I'm about to start a research project that involves creating a complete database documenting and classifying all 2-state, 2-symbol Turing machines, according to a ...
0
votes
1answer
59 views

Halting problem reduction to Halting for all inputs

I was going through my book of revision and I would like someone hints on this. The Halt for All Input problem (HAI) takes a machine and tell if this machine halts or not for any input We prove it ...
0
votes
1answer
64 views

Halting problem reducing to the blank tape halting problem

I was going through my book of proof and I find very confusing its definition, so I would like someone to help me in understanding this. The blank tape problem takes a machine and an empty tape and ...
3
votes
2answers
92 views

Halting Problem and Turing Degree and Reduction? [closed]

This is a Local Olympiad question on computation and computer science on 2013. How can explain it and says some hint for understanding such an example question. for $ A \subseteq \mathbb{N}$ we ...
1
vote
3answers
64 views

Language is recursive, hence recursively enumerable

I was going through a book of proof and I read: If L is recursive, L is r.e. And the proof goes: Let L be recursive, hence there is a TM that decides it Convert an halt state to a normal state ...