turing-machines Questions
13
Solved
When have you ever personally come upon the halting problem in the field? This can be when a co-worker / boss suggested a solution which would violate the fundamental limits of computation, o...
Neff asked 25/10, 2008 at 6:8
3
Solved
I've studied the basic turing machine theory as an undergraduate. I never saw any mention of a timed turing maching. An example: a turing machine that counts the number of seconds passed since it s...
Vinegarette asked 22/6, 2012 at 22:57
2
Solved
The definitions of Turing Machine say that it is prohibited for one to read/modify it's instruction table (program). Exactly, Turing Machine has no access to it's own program.
What benefits can be...
Androgyne asked 8/10, 2009 at 4:29
2
I know that in turing machines, the (different) tapes are used for both input and output and for stack too. In a problem of adding 2 numbers using turing machine, the input is dealing with many sym...
Hickox asked 9/9, 2011 at 18:43
2
Solved
I have to determine whether a language (for example L={a^n b^m c^s | 0<=n<=m<=s}) is regular, context-free, recursive, recursively enumerable or none of them.
I know how to determine if a...
Barrada asked 16/2, 2011 at 17:58
5
Solved
I was recently reading about artificial life and came across the statement, "Conway’s Game of Life demonstrates enough complexity to be classified as a universal machine." I only had a rough unders...
Totally asked 27/12, 2008 at 12:36
4
Solved
Regular expressions are often pointed to as the classical example of a language that is not Turning complete. For example "regular expressions" is given in as the answer to this SO question looking...
Telfore asked 29/1, 2011 at 6:52
7
Solved
If I have a machine, call it machine 1, that is able to solve a problem: it's just a machine, not per se a Turing machine. It can solve one specific problem.
If this exact same problem can be solve...
Naturopathy asked 20/1, 2010 at 12:10
2
I am now taking a course on Theory of Computation. I can understand the concepts well. I can able to solve the problems. And, when I asked my instructor about the real world application, he told me...
Interrupt asked 18/9, 2011 at 3:34
2
Solved
I think defenitions of time complexity and space complexity for Turing machines are identical and I can't differentiate
between them.
Please help me. Thanks.
Rico asked 21/8, 2011 at 8:18
1
Solved
Is the following language L undecidable?
L = {M | M is a Turing machine description and there exists an input x of length k such that M halts after at most k steps}
I think it is but I couldn'...
Acrimonious asked 10/7, 2011 at 13:39
3
Solved
I found a Wikipedia article of a list of Turing machine equivalents. However, it doesn't tell a method of how to determine whether a given machine is Turing machine equivalent.
Do I need to use th...
Comeaux asked 10/1, 2011 at 9:18
2
Solved
While reading the reviews for Stephen Wolfram's "A New Kind of Science" on Amazon, I came across the following statement:
Every computer science (CS) student knows the dovetailer, a very simple ...
Marin asked 24/2, 2011 at 16:3
3
I happen to need an algorithm for a turing machine that reads a string of 0's and then writes on the tape how many there were in binary.
I realize that in practice the machine won't actually count...
Halfblooded asked 11/1, 2011 at 19:5
1
Solved
AFAIK, turing computable numbers are numbers whose i-th index can be returned by a Turing Machine. So a non-computable number would be something like a number whose decimal points are decided...
Heritor asked 9/11, 2010 at 13:43
6
Solved
these days I have been studying about NP problems, computational complexity and theory. I believe I have finally grasped the concepts of Turing Machine, but I have a couple of doubts.
I can accept...
Noam asked 14/9, 2010 at 22:9
2
Solved
I know a little about what is a turing-machine and a turing-complete language, but to understand better, could someone give examples of languages that are not Turing complete? (maybe even machines ...
Gamesmanship asked 30/8, 2010 at 12:34
4
Solved
If you take the original Turing machine definition as follows:
...an infinite memory capacity
obtained in the form of an infinite
tape marked out
into squares, on each of which a symbol coul...
Sil asked 21/8, 2010 at 12:58
3
Solved
For the uninitiated, Brainfuck is a Turing-complete language with only 8 commands, all of which have literal equivalents in C:
bf c
----------------------
> ++ptr;
< --ptr;
+ ++*ptr;
- --*pt...
Hydrogenize asked 6/8, 2010 at 6:1
2
Solved
I was having a discussion earlier about a state machine, and there was a question as to whether it might not halt on some input. It seems like a property of state machines that is important and fre...
Virgilio asked 24/6, 2010 at 19:2
4
Solved
I understand they aren't real and they seem to branch computation whenever there are 2 options, instead of picking one. But, for example, if I say this:
"Non deterministically guess a bijection p ...
Uro asked 25/1, 2010 at 14:33
3
Solved
I'm trying to learn some aspects of the Chomsky Hierarchy which are related to programming languages, and i still have to read the Dragon Book.
I've read that most programming languages can be par...
Grimmett asked 28/5, 2010 at 13:47
3
Solved
Whilst doing exam revision I am having trouble answering the following question from the book, "An Introduction to the Theory of Computation" by Sipser. Unfortunately there's no solution to t...
Selftaught asked 12/3, 2010 at 20:20
2
Solved
There are languages that a Turing machine can handle that an LBA can't, but are there any useful, practical problems that LBAs can't solve but TMs can?
An LBA is just a Turing machine with a finit...
Evie asked 26/1, 2010 at 22:34
12
Solved
Ok guys, today's goal is to build a Turing machine simulator. For those that don't know what it is, see the Wikipedia article. The state table we are using today is found at the end of the Fo...
Chrysolite asked 22/11, 2009 at 2:11
© 2022 - 2024 — McMap. All rights reserved.