Некоторые расширения/варианты машин Тьюринга (теория вычислений)

В сегодняшней лекции мы рассмотрим некоторые варианты или расширения машин Тьюринга и введем понятие вычислительной эквивалентности, которое мы подробнее рассмотрим в будущих лекциях. То есть, существуют ли различные вычислительные модели, даже путем модификации нашего определения машины Тьюринга, которые обладают такими же или одинаковыми вычислительными возможностями (способностью решать задачи)? Мы начнем с нескольких примеров способов проектирования машины Тьюринга, перейдем к простому в использовании примеру с «опцией сохранения» [то, что мы хотели бы иметь в нашей машине Тьюринга], к более простым версиям машины Тьюринга, а затем к более сложному примеру, как и в случае с машинами Тьюринга (например, k-ленточная машина Тьюринга, также известная как многоленточная машина Тьюринга). На этом обсуждение не закончится. Временные метки: 0:00 Начало лекции 0:09 Напоминание о том, на каком этапе мы находимся. 0:40 Основные идеи, введение в вычислительную эквивалентность, несколько базовых примеров вариантов. 11:59 Что мы подразумеваем под вычислительной эквивалентностью в этом контексте («одинаковая мощность», рабочее определение)? 17:27 Машины Тьюринга с опцией «Остаться» (как это «имитировать») 32:46 А что, если мы ограничим возможности машины Тьюринга? Несколько примеров. 41:27 Многоленточные машины Тьюринга и как они работают. 53:19 Заключение Желаю вам прекрасного дня! Подписчики (на момент публикации, по уровням (сверху вниз)): ---------------------------------------------------------- Подписчики Patreon (общая поддержка): Draikou Подписчики Patreon (базовая поддержка): Tor Asbjørn Подписчики Subscribestar (особая благодарность и доступ для подписчиков!) Ibrahim#582e0bc4 ----------------------------------------------------------- Станьте подписчиком сегодня! Чтобы поддержать мою работу и миссию по предоставлению бесплатного и доступного образования в области компьютерных наук (особенно в теории), подпишитесь на канал и поделитесь моими видео. Пожалуйста, сделайте пожертвование и поддержите мою работу, чтобы я мог создавать больше контента: PATREON:   / pagewizard   SUBSCRIBESTAR: https://www.subscribestar.com/drpage PAYPAL: https://paypal.me/pagewizard Также следите за мной: FACEBOOK:   / danielrpage   TWITTER:   / pagewizardgle   QUORA: https://www.quora.com/profile/Daniel-... TWITCH:   / pagewizard   #Информатика #МашиныТьюринга #ТеорияВычислений