­čľą´ŞĆUniversal Turing Machine

by Stephen Shank

Version 4 (November 20, 2018)

Download (327 downloads)

UPDATE: Multiple tapes supported now.

A program that runs Turing Machine programs defined as a start state, accept state(s), and a set of transitions.

- Comes with 6 programs:
* BinaryPalindrome: Will halt on the accept state if the input is a binary palindrome like 1001, otherwise it will halt in a reject state.
* BinaryIsOdd: Determines whether the given binary number is odd. If so it will halt in the accept state.
* BinaryFlip: Will flip all of the bits in a given binary number, then halt in the accept state.
* BinaryAddSingle: Binary Addition on a single tape. Enter something like 101#1110 and the output will be the sum, i.e.10011. This is very inefficient, because it works by decrementing the first number and incrementing the second, one at a time until the first number is zero.
* BinaryAddMultiple: Binary Addition on two tapes. The input and output is the same as for BinaryAddSingle. More efficient and also no restriction on leading zeros in this program.
* UTuringMachine: This program, as the name implies, takes an encoded form of a (single tape) Turing Machine Program along with the input for that program, and runs the program on the input. This is much much slower than just running one of those programs directly in this flow: because hashing isn't possible, the transition table must be checked one at a time until a matching state and input are found. See comments on that program for more info.

- Run programs on any input. The tapes are infinite for all reasonable intents and purposes. The only limitation is that " ", ",", ":", and ";" will always lead to the reject state, and will never be written by the Turing Machine's head. When running press auto to watch the machine execute once a second, or skip to run 100 steps before displaying the TM.

- Edit programs or create your own: While it is certainly possible to make your own properly formatted program to use in a basic text editor, the included editor makes it more difficult to make mistakes and explicitly tells you what you are entering at each step.

- Supports any finite number of tapes, although it will definitely be harder to understand the more tapes you add.

- Added support for execution on multiple tapes. Default is still 1.
- Added two new example programs demonstrating the use of multiple tapes: BinaryAddMultiple and UTuringMachine.
- Added some new features to the TM maker:
* Select cancel to delete a comment and OK to leave it the same or edit it.
* When selecting more than one lines in the editor, every line except the last will be shifted down by one, and the last line will replace the first line.
* You can now select multiple states or multiple transitions to delete them.
* Support for multi-tape TMs: Enter the input characters for each tape one at a time, then the next state, then an output character and a direction to move the head for each tape one tape at a time.
- Various text improvements and optimizations.

4.8 average rating from 5 reviews

5 stars
4 stars
3 stars
2 stars
1 star

Rate and review within the app in the Community section.