The Halting Problem of Computer Science, aka, the Busy Beaver

1. You'll be watching a video and
2. playing a game

The Halting game

Description

You will be playing the role of a special Turing Machine (TM). Let's called it The Oracle

The essence of the game is as follows: you will be provided with the set of rules of a TM as well as a given tape with a given content. Your task is to say whether that TM that you were given with that tape that you were given, the whole thing, will halt (stop) or not.

The rules you must follow are the following:

1. If that TM with that tape content will not stop ever, you say NO
2. If that TM with that tape content will stop, you say NOTHING, stay silence, do not even blink,...no matter how much persistently we are asking you

Examples:

What will your answer be if you are given with the following TM+tape? (Answer: NO, because the following TM will not halt ever, i.e., will keep running forever)

• TM rules: If it reads a 1; leave it as it is and move one to the right
• TM rules: If it reads a 0; write a 1 and move one to the right
• TAPE content: 0 1 0 0 1 1 1 0 1

What will your answer be if you are given with the following TM+tape? (Answer: -silence- because this TM will stop after it reads that 3rd consecutive towards the end of the tape)

• TM rules: If it reads a 0; write a 1 and move one to the right
• TM rules: If it reads 3 consecutive 1's; leave it as it is and HALTS
• TAPE content: 0 1 0 0 1 1 1 0 1

ASSIGNMENT:

A) What will your answer be if you are given with the following TM+tape?

• TM rules: If you read in the description of a TM and a tape, and that TM with that tape would halt, you SAY NOTHING, no matter how much we insist in asking you.
• TM rules: If you read in the description of a TM and a tape, and that TM with that tape would NOT halt, you SAY NO! It doesn't halt.
• TAPE content: The description of the TM given in example 2

B) What will your answer be if you are given with the description of the TM of example 1?