Практическая работа №1

1. Составить алгоритм сложения натуральных чисел.

	_
	V	V			V	V	V

2. Составить алгоритм прибавления к любому натуральному числу единицы.

		_
			V	V	V

			_
			V	V	V

					_
			V	V	V

3. Составить алгоритм вычитания единицы от любого натурального числа.

		_
			V	V	V

			_
			V	V	V

					_
			V	V	V

4. Составить алгоритм написания на пустой ленте числа 0; 1; 2; 3; 4.

5. Пусть на ленте имеется запись из нескольких меток подряд. Каретка находится над самой крайней правой помеченной ячейкой. Составить алгоритм нахождения ближайшей пустой ячейки слева.

   								_
   			V	V	V	V	V	V

6. Пусть на ленте имеется запись из нескольких меток подряд. Каретка находится над самой крайней левой помеченной ячейкой. Составить алгоритм нахождения ближайшей пустой ячейки справа.

			_
			V	V	V	V	V	V

7. Составить алгоритм нахождения ближайшей помеченной ячейки.

			_
						V	V	V

							_
			V	V

8. Составить алгоритм удаления всех меток на ленте.

	_
			V	V	V	V	V	V

								_
			V	V	V	V	V

3. Формализация понятия алгоритма посредством машины Тьюринга

В 1936 г. Аланом Тьюрингом для уточнения понятия алгоритма был предложен абстрактный универсальный исполнитель. Его абстрактность заключается в том, что он представляет собой логическую вычислительную конструкцию, а не реальную вычислительную машину. Термин «универсальный исполнитель» говорит о том, что данный исполнитель может имитировать любой другой исполнитель. Например, операции, которые выполняют реальные вычислительные машины можно имитировать на универсальном исполнителе. В последствие, придуманная Тьюрингом вычислительная конструкция была названа машиной Тьюринга. Кроме того, предполагается, что универсальный исполнитель должен уметь доказывать существование или отсутствие алгоритма для той или иной задачи.