My Math Forum  

Go Back   My Math Forum > College Math Forum > Applied Math

Applied Math Applied Math Forum


Reply
 
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 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.
Christi123 is offline  
 
April 14th, 2008, 04:33 AM   #2
Global Moderator
 
CRGreathouse's Avatar
 
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.
CRGreathouse is offline  
Reply

  My Math Forum > College Math Forum > Applied Math

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





Copyright © 2019 My Math Forum. All rights reserved.