My Math Forum Help On Turing Machine Problems Please

 Applied Math Applied Math Forum

 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 non-blank 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 non-blank, or if it is currently scanned, or if it lies between two squares each currently non-blank 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:
 Originally Posted by Christi123 2. Let us call any square on a tape currently significant if it is currently non-blank, or if it is currently scanned, or if it lies between two squares each currently non-blank 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.
If there are 100 significant squares, then they are no further left or right than 100 from the initial square. Thus there are (# symbols)^201 possible tapes (a finite number), and 201 * (# symbols)^201 possible tape + position combinations. The TM must halt, leave the area, or repeat one of these combinations within 201 * (# symbols)^201 steps.

 Tags machine, problems, turing

 Thread Tools Display Modes Linear Mode

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

 Contact - Home - Forums - Cryptocurrency Forum - Top