Hide

Problem E
Turing Machine Cube Recognizer

/problems/baylor.tmcubes/file/statement/en/img-0001.jpg
Photo by Rocky Acosta

For this problem, write an algorithm that uses just the basics of a Turing machine to recognize when its input is a string of the symbol ‘a’ whose length is a cube. For example, it should accept ‘a’ and ‘aaaaaaaa’, while rejecting ‘aaa’ and ‘aaaaa’.

Use only the TuringMachineTape and TuringMachineUtility classes provided as included code. You may write functions, but you may not use the following typical programming features:

  • Do not use any arithmetic operations (e.g. +, ++, -, --, *, etc.) bitwise operations (e.g. |, &, etc.), bit shifting operations (e.g. >>, <<), or inequality operations (e.g. <, >).

  • Do not allocate any memory dynamically (except what is necessary to create TuringMachineTape objects).

  • Do not use recursion (you may write and use functions, however).

You will observe that the TuringMachineTape class uses dynamic memory allocation and arithmetic operators in its implementation; you just can’t use these programming language features in your code.

The only types you will need to use are char, int and boolean. You can call the special method TuringMachineTape.accept() to accept, and use TuringMachineTape.reject() to reject.

Observe that the TuringMachineTape class has a constructor that can read its input from standard input. This will let you read a whole line of input without using arrays, strings or arithmetic. Since we can’t use strings or arrays, you will want to initially read the input using this constructor.

Have a look at the TuringMachineUtility class for a description of how you might write subroutines that make some things easier when working with tapes. You may write any code you want (including extra methods) within these guidelines.

Input

Input contains one line containing between $0$ and $25\, 000$ copies of the letter ‘a’.

Output

Output accept if the string has cubic length; reject otherwise.

Sample Input 1 Sample Output 1
a
accept
Sample Input 2 Sample Output 2
aa
reject
Sample Input 3 Sample Output 3
aaaaaaaaaaaaaaaaaaaaaaaaaaa
accept
CPU Time limit 3 seconds
Memory limit 1024 MB
Statistics Show
Author
Greg Hamerly
Source Baylor University Introduction to Computation Theory
License Creative Commons License (cc by-sa)

Please log in to submit a solution to this problem

Log in