CIS 115

Universal Computers

What is a Universal Computer?

What is a Universal Computer?

A universal computer can simulate ANY other real-world computer given infinite time and infinite memory

Turing Machine Instructions

Turing Machine Example

Start with 2 items on a tape

1. If 1, go to #5
2. Move left
3. If 0, go to #9
4. If 1, go to #6
5. Move Left
6. Move Left
7. Write 1
8. Stop
9. Move Left
10. Write 0
11. Stop

∨ Or

Turing Machine Example

Start with 2 items on a tape

1. If 0, go to #7
2. Move left
3. If 0, go to #8
4. Move Left
5. Write 1
6. Stop
7. Move Left
8. Move Left
9. Write 0
10. Stop

∧ And

Assignments

• Read and be prepared to discuss:
  • Pattern on the Stone Chapter 5: Algorithms & Heuristics
• Blog 2: Algorithms - Due Monday 9/19 10PM
• ATM Project - Due 9/13 10PM

Blog 2: Algorithms

There are many important algorithms in Computing Science. In fact, we’re going to learn about many of them later in this class. For now, however, I’d like you to pick an algorithm from Wikipedia’s list of algorithms (https://en.wikipedia.org/wiki/List_of_algorithms) and write about it. Some things you can cover:

• Where did this algorithm come from?
• How does it work?
• What makes it special or unique?
• Are there other algorithms that achieve the same or similar outcome?
• Could you do this algorithm manually? Or does it require a computer?
• How does this algorithm relate to what we’ve already read in the textbook? Did the textbook help you understand how this algorithm works? (textbook references)
• Where can this algorithm be found in the real world? (outside reference)

Lists in Scratch

Get an Item

Set an Item

Turing Machine Blocks

Turing Machine - Invert Bits