История изменений
Исправление quasimoto, (текущая версия) :
Бесконечность она в математике разная бывает, и просто сказать «бесконечная лента» недостаточно
http://www.andrew.cmu.edu/user/avigad/Teaching/candi_notes.pdf
The machine has a two-way infinite tape with discrete cells. Note that “infinite” really means “as big as is needed for the computation”; any halting computation will only have used a finite piece of it.
The textbook describes Turing machines with only two symbols, 0 and 1; but one can show that with only two symbols, it is possible to simulate machines with more. Similarly, some authors use Turing machines with “one-way” infinite tapes; with some work, one can show how to simulate two way tapes, or even multiple tapes or two-dimensional tapes, etc.
Такая же бесконечность, что и в случае натуральных (one-way tapes) и целых чисел (two way tapes, и изоморфных — помноженных декартово на конечные множества (больше алфавита), на те же бесконечные (two-dimensional tapes), параллельно (multiple tapes)) — любая программа за конечное число шагов потребует конечного, но сколь угодно большого куска ленты, как и любое целое число не бесконечно, но всего их бесконечно много.
неполнота связана с использование бесконечно большого числа(из мат. анализа) при анализе МТ и проблемы её останова.
Вообще первая теорема о неполноте следует из проблемы останова — http://www.scottaaronson.com/blog/?p=710, а сама она — http://www.bemuzed.com/lucasd/halting-poem.html :)
Исправление quasimoto, :
Бесконечность она в математике разная бывает, и просто сказать «бесконечная лента» недостаточно
http://www.andrew.cmu.edu/user/avigad/Teaching/candi_notes.pdf
The machine has a two-way infinite tape with discrete cells. Note that “infinite” really means “as big as is needed for the computation”; any halting computation will only have used a finite piece of it.
The textbook describes Turing machines with only two symbols, 0 and 1; but one can show that with only two symbols, it is possible to simulate machines with more. Similarly, some authors use Turing machines with “one-way” infinite tapes; with some work, one can show how to simulate two way tapes, or even multiple tapes or two-dimensional tapes, etc.
Такая же бесконечность, что и в случае натуральных и целых чисел (и изоморфных — помноженных декартово на конечные множества (больше алфавита), на те же бесконечные (two-dimensional tapes), параллельно (two way tapes)) — любая программа за конечное число шагов потребует конечного, но сколь угодно большого куска ленты, как и любое целое число не бесконечно, но всего их бесконечно много.
неполнота связана с использование бесконечно большого числа(из мат. анализа) при анализе МТ и проблемы её останова.
Вообще первая теорема о неполноте следует из проблемы останова — http://www.scottaaronson.com/blog/?p=710, а сама она — http://www.bemuzed.com/lucasd/halting-poem.html :)
Исходная версия quasimoto, :
Бесконечность она в математике разная бывает, и просто сказать «бесконечная лента» недостаточно
http://www.andrew.cmu.edu/user/avigad/Teaching/candi_notes.pdf
The machine has a two-way infinite tape with discrete cells. Note that “infinite” really means “as big as is needed for the computation”; any halting computation will only have used a finite piece of it.
The textbook describes Turing machines with only two symbols, 0 and 1; but one can show that with only two symbols, it is possible to simulate machines with more. Similarly, some authors use Turing machines with “one-way” infinite tapes; with some work, one can show how to simulate two way tapes, or even multiple tapes or two-dimensional tapes, etc.
Такая же бесконечность, что и в случае натуральных и целых чисел (и изоморфных — помноженных декартово на конечные множества (больше алфавита), на те же бесконечные (two-dimensional tapes), параллельно (two way tapes)) — любая программа за конечное число шагов потребует конечного, но сколь угодно большого куска ленты.
неполнота связана с использование бесконечно большого числа(из мат. анализа) при анализе МТ и проблемы её останова.
Вообще первая теорема о неполноте следует из проблемы останова — http://www.scottaaronson.com/blog/?p=710, а сама она — http://www.bemuzed.com/lucasd/halting-poem.html :)