
Applied Math Applied Math Forum 
 LinkBack  Thread Tools  Display Modes 
April 14th, 2008, 03:46 AM  #1 
Newbie Joined: Mar 2008 Posts: 11 Thanks: 0  Help On Turing Machine Problems Please
Hello, Can someone help me on these problems please ? 1. Consider the task of deciding if any given Turing Machine (TM) will from an initial blank tape ever print a nonblank on the initially scanned square. Assuming the Blank Tape Halting Problem (BTHP) Theorem, show that this task is Turing Impossible. 2. Let us call any square on a tape currently significant if it is currently nonblank, or if it is currently scanned, or if it lies between two squares each currently nonblank or scanned, and consider the task of deciding if any given TM from an initially blank tape will ever have more than 100 currently significant squares on its tape. Show that this task is Turing Possible. 
April 14th, 2008, 04:33 AM  #2  
Global Moderator Joined: Nov 2006 From: UTC 5 Posts: 16,046 Thanks: 938 Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms  Re: Help On Turing Machine Problems Please Quote:
 

Tags 
machine, problems, turing 
Thread Tools  
Display Modes  

Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Turing Machine  krausebj0  Number Theory  1  June 28th, 2013 04:01 AM 
Turing machine  jenifer  Applied Math  1  December 28th, 2011 11:08 AM 
Turing machine 2  jenifer  Applied Math  0  November 2nd, 2011 07:50 AM 
Turing Machine Problem... Help please  ikurwa  Applied Math  0  April 16th, 2011 10:37 PM 
A Turing Machine Question  Christi123  Applied Math  0  March 22nd, 2008 03:25 PM 