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

learn more… | top users | synonyms

2
votes
1answer
22 views

Is there an example of a recursive language which is not context sensitive?

I have been looking for a prototypical language for recursive languages (decidible) which is no context sensitive without success. For instance $a^*$ is prototypical of regular languages, $a^nb^n$ for ...
-2
votes
1answer
42 views

How can a Turing machine accept infinite number of inputs?

How it is possible for a turing machine to process an infinitely long input ?
-1
votes
1answer
46 views

Turing tests and humans

How are the questions framed in Turing tests? I mean what factors would one consider before framing questionnaire for the Turing Test.How the questions should be framed to make the test unbiased for a ...
3
votes
1answer
85 views

Whatever that can be done using algorithm can be done using Turing machine

In 1937 how was Alan Turing so sure that all that can be done using algorithms can be implemented using a Turing machine? Since that period many new algorithms were implemented. What was his ...
0
votes
1answer
91 views

Prove whether this problem is decidable or undecidable

So I am reviewing my notes for this problem, and I cant seem to understand how this problem works. Say we have M, and M accepts an input that makes it visit every non-halting state. I convinced ...
0
votes
0answers
39 views

Does Turing Completeness imply the existence of a Universal Program?

Please correct me if at any time my definitions are wrong. Suppose we have a programming language $L$ over some set $D$ with semantic (partial) n-ary functions $\varphi^n:D \to (D^n \to D)$. Assume $L ...
0
votes
0answers
35 views

How do I show that M1, M2 are two Turing machines such that L(M1) ⊆ L(M2)?

I am currently studying for a midterm tomorrow and my professor gave us links to backtests online. This is problem #3 in the following back quiz: ...
-3
votes
1answer
48 views

Prove that TM does not decide this language

So my problem is how can I show that this TM does not decides this language. $$L = \{a^nb^nc^n\ |\ n \geq 0\} $$ It might be a basic problem and seem silly to you but still I do not know how to ...
1
vote
2answers
41 views

Turing machine states, lost in the jungle

There is a lengthy discussion going on at the English Language & Usage StackExchange site suggesting various synonyms for dead code, and it got me wondering about an angle that wasn't covered -- ...
1
vote
1answer
41 views

A question about halt (or stop) of Turing machine

I try to understand something: At Turing machine we have two stats: $q_{accept}$ and $q_{reject}$. Now, if machine $M$ runs on word $w$ (I hope I write it right...) and the final configuration is: ...
0
votes
1answer
33 views

Turing Machines: decidability and bounds checking

I am wanting to show that it is decidable that a Turing machine M, on input w, ever attempts to move its head past the right end of the input string w. I'm assuming I construct a TM which shifts the ...
0
votes
0answers
35 views

Is there a name for a useful Turing-like machine that is more powerful (meaning accepts more languages) than a Turing machine?

Disclaimer: I'm a software engineer with only an undergrad education and have never published or anything so please forgive any minor notation or jargon blunders - but of course feel free to point ...
1
vote
0answers
20 views

Decidability Proof of $A_{Cfg}$

I am a beginner to complexity theory and I came up with the following proof of decidability of $A_{Cfg}$ = {$<G,w>|G$ is a context free grammar that generates string $w$} The Turing machine ...
1
vote
0answers
30 views

Busy beaver construction system [closed]

I want to construct a busy beaver TM which has the alphabet $\Sigma = \{1,2, X\}$ and $X$ is the blank symbol. I want to do this using 3, 4 and 5 states (means one just for halting, so 3 states = 2 ...
6
votes
1answer
120 views

Prove n! is fully time constructible

We just finished our "Time constructability" lesson in class last week, and we, for example's sake, showed that $n^k, 2^n$ are fully time constructible, i.e. there exists a (multi-tape deterministic) ...
4
votes
0answers
28 views

Why does using an encoding trick like Gödel numbers make a register machine universal?

Here the author describes the Random Access Stored Program machine and the problem of indirect addressing. The author states: But this does not solve the problem (unless one resorts to Gödel ...
-2
votes
0answers
21 views

Is the class of deciders of context-free languages semi-decidable? [duplicate]

Can anyone help me to prove/disprove that: $CFL_{TM} \in \text{co-RE}$ where $$ CFL_{TM}=\{\langle\,M\,\rangle\mid L(M) \text{ is context free language and $M$ is a TM}\}$$
0
votes
1answer
47 views

A recursive language minus a recursively enumerable language results in a recursive language?

I know that a recursively enumerable language minus a recursive language results in a recursively enumerable language, but I'm confused with the above question. Aren't all recursive languages also ...
26
votes
4answers
5k views

Theoretical machines which are more powerful than Turing machines

Are there any theoretical machines which exceed Turing machines capability in at least some areas?
2
votes
1answer
73 views

How to find left-hand side of tape on a Turing Machine?

I am pretty new to Turing Machines and am trying to figure something out. So let's say I have a tape with input 0 0 1 0 0 1 The language is twice as many 0's ...
2
votes
1answer
30 views

How to write the turing machine processing operations?

I have this Turing machine example given in my book: For the language $0^n1^n$. I understand how it works because it's very similar to a Finite State Machine. But what I want to know is the ...
1
vote
1answer
40 views

Implementation-level description of a Turing Machine

I am new to Turing Machines! I need to work on an implementation-level description of a Turing machine that decides the language L = an where n is a Fibonacci number. I know Fibonacci numbers ...
0
votes
0answers
143 views

Trying to show if two languages are recognizable or not

I have two languages that I am trying to prove are recognizable or not: Let L1 = {<\M, w> : M is a Turing machine that accepts string w and does not accept string ε}. Is L1 recognizable? Prove ...
3
votes
1answer
32 views

Unary notation representation in Turing Machine

What can be a good convention to represent positive and negative integers in unary notation on a Turing machine? I want to design a Turing machine which acts as a subtractor.So should I partition the ...
3
votes
1answer
54 views

Kolmogorov complexity vs purposefully inefficient Turing machines

It's a theorem that, although the Kolmogorov complexity of a string is relative to the Turing machine you're working with, it differs by at most a constant (basically the amount of space it takes to ...
3
votes
1answer
36 views

Linear Bounded Automaton that accepts all strings

I'm currently reading Sipser's Introduction to the Theory of Computation, and I'm reading up about linear bounded automata, now we know from Rice's Theorem that whether a TM can accept all strings in ...
1
vote
1answer
53 views

Non deterministic turing machine

Does a non deterministic turing machine which is a decider halt on all branches for all inputs?? I know it must halt on all branches for a string not in language but for a string in language ,NDTM ...
1
vote
1answer
19 views

Wang tile turing machine tile placement

I've read numerous links on the fact that wang tiles are turing complete, and details about them (links at end). However there is little talk of how to actually place the tiles. One place i read ...
2
votes
1answer
31 views

Does the Kolmogorov complexity of a program $p$ generating a string $x$ equal the complexity of $x$ up to constant?

If $U$ is a universal prefix Turing machine, $U(p)=x$ for some program $p$ and string $x$, is it true that $K(x)=K(p)+O(1)$, with $K$ being the prefix Kolmogorov complexity?
1
vote
1answer
68 views

Proving a language is neither Recursively Enumerable nor co-Recursively Enumerable

$$L = \{ \langle M \rangle \mid \text{\(M\) is a Turing Machine and \(|L(M)| = 1\)} \}$$ I have to prove that this is not R.E. and not co-R.E. I know how to approach these kind of problems. For ...
1
vote
1answer
77 views

In this proof that sokoban+ is pspace complete, how does the gadgets register the fact that a cell of the turing machine has changed?

I´ve been reading the paper "SOKOBAN and other motion planning problems" by Dorit Dor and Uri Zwick. This is a link to the paper: Sokoban+ is pspace complete In the paper, they proved that a ...
1
vote
1answer
49 views

Universal memcomputing machines (UMM)

This paper on memcomputing seems like a really big deal, but it doesn't seem to be particularly popular. They prove that their UMM can solve NP problems in P, although they don't claim P = NP. In ...
3
votes
1answer
259 views

Show that the Halting problem is reducible to its complement

HALT$_{TM}$ is the set of all machine-input pairs $<M,w> $ where $M$ halts on input $w$ The complement of HALT$_{TM}$ is the set of all machine-input pairs $<M,w> $ where $M$ ...
1
vote
1answer
33 views

Is there a complexity metric for finite state machines?

I'm working on evolving Turing machines (with binary symbols / infinite tape) for simple operations (e.g. sorting) using genetic algorithms. I'm interested in using the complexity of the FSM for each ...
2
votes
0answers
28 views

Problems understanding proof of smn theorem using Church-Turing thesis

I am reading Barry Cooper's Computability Theory and he states the following as the s-m-n theorem: Let $f:\mathbb{N}^2\mapsto\mathbb{N}$ be a (partial) recursive function. Then there exists a ...
3
votes
0answers
36 views

Random Access Machine output

It is known that when a Random Access Machine halts the output on the registers is going to be $R_1,\ldots,R_{||R_0||}$ after going through its instruction set where $||R_0||$ denotes the length of ...
0
votes
1answer
61 views

ETM Undecidability

I'm having trouble convincing myself of the proof for the following theorem: ETM = { <M> | M is a TM and L(M) = ∅} is undecidable. I think I understand ...
4
votes
2answers
261 views

NSPACE for checking if two graphs are isomorphic

I was studying nondeterministic Turing Machines and came across the following question: Describe a nondeterministic Turing Machine (NTM) that only accepts two graphs (G1 and G2) if they are ...
1
vote
2answers
63 views

Universal Multi Head Turing Machine

It is common knowledge that a universal Turing machine can simulate any Turing machine with logarithmic overhead. Is it possible to make this overhead constant by constructing an analogous "Universal" ...
3
votes
1answer
134 views

Are all partial functions partial computable?

If we have some function $f\colon \mathbb{N} \rightarrow \mathbb{N}$ that is not total, i.e. for some values $x \in \mathbb{N}$, $f(x) = {\perp}$, is $f$ always partial computable? By partial ...
3
votes
1answer
50 views

Examples of languages not decidable by a TM using certain upper bounds on space/time

I'm learning about time and space complexity involving Turing Machines at the moment, and would really like some concrete examples of specific languages that belong (or don't belong) to certain ...
-2
votes
1answer
56 views

Proof that {(M,w) | M accepts a prefix of w} is RE

Can someone help me go over that the following language can be recognized by a Turing Machine? $$L = \{\langle M,w\rangle \mid M \text{ accepts a prefix of } w\}$$ We can construct a universal ...
3
votes
2answers
44 views

Turing machine enumerator

As the number of Turing Machines is countably, we can create some list of them and number them 1, 2, 3,... Suppose turing machine k computes some function $f_k$. Is there a turing machine S that ...
1
vote
1answer
102 views

Proof by Reduction: From Empty Language to Halting Problem on Empty Input

Question: Let language $E$ = {$\langle M \rangle$ | $M$ accepts no inputs whatsoever} Let language $H$ = { $\langle M \rangle$ | $M$ halts on an empty string input}. Is it possible to show that $H$ ...
1
vote
2answers
43 views

Turing machine that can tell if it ends in standard position?

Suppose we have a TM $M$ with alphabet $\{0, 1 \}$ with n states. Say $M$ halts in standard position if it is scanning the left-most $1$ of a non-broken string of $1$s (and everything else on the tape ...
1
vote
1answer
235 views

Finite State Machine that only accepts strings with equal number of 0's and 1's

Question: Suppose you have a finite state machine that accepts only strings with an equal number of zeros and ones. Show that you can then construct a finite state machine that accepts only strings of ...
0
votes
0answers
16 views

Pointer Machine Graph double string

I was wondering if there was a logarithmic analogue to the Turing machine Palindrome problem that could be run in logarithmic time (multi head TM). That is, on input tape with a string $S$, it ...
2
votes
1answer
96 views

Why is simulation by non deterministic Turing machine faster than a deterministic one?

A deterministic universal Turing machine $U_D$ can simulate a deterministic turing machine $M_D$ in $O(T(n)log(T(n)))$ where $M_D$ runs in $O(T(n))$. But I came across an exercise in Sanjeev Arora and ...
1
vote
1answer
64 views

Why is universal turing machine considered with only one head?

While defining the following time hierarchy theorem (for deterministic case ) : If $f(n)\log{f(n)}=o(g(n))$ then there are languages decidable in $O(g(n))$ which cannot be decided in $O(f(n))$ ...
0
votes
1answer
35 views

Certificate Definition of NL

As per the Sanjeev Arora book, for a certificate based definition of $NL$, the machine is allowed a "read-once" certificate tape to store the certificate along with $O(log n)$ read/write work tape for ...