Re: Dlaczego dowód na nierozstrzygalność problemu stopu jest błędny

eGospodarka.pl › Grupy › pl.comp.programming › Dlaczego dowód na nierozstrzygalność problemu stopu jest błędny › Re: Dlaczego dowód na nierozstrzygalność problemu stopu jest błędny

Path: news-archive.icm.edu.pl!news.gazeta.pl!newsfeed.pionier.net.pl!news.glorb.com!p
ostnews.google.com!f6g2000yqa.googlegroups.com!not-for-mail
From: "Marcin 'Qrczak' Kowalczyk" <q...@k...org.pl>
Newsgroups: pl.comp.programming
Subject: Re: Dlaczego dowód na nierozstrzygalność problemu stopu jest błędny
Date: Thu, 19 Aug 2010 08:58:51 -0700 (PDT)
Organization: http://groups.google.com
Lines: 27
Message-ID: <8...@f...googlegroups.com>
References: <8...@t...googlegroups.com>
NNTP-Posting-Host: 83.4.195.125
Mime-Version: 1.0
Content-Type: text/plain; charset=ISO-8859-2
Content-Transfer-Encoding: quoted-printable
X-Trace: posting.google.com 1282233531 17625 127.0.0.1 (19 Aug 2010 15:58:51 GMT)
X-Complaints-To: g...@g...com
NNTP-Posting-Date: Thu, 19 Aug 2010 15:58:51 +0000 (UTC)
Complaints-To: g...@g...com
Injection-Info: f6g2000yqa.googlegroups.com; posting-host=83.4.195.125;
posting-account=Y4cAXQoAAAAv8UBiA5Li4Y_naLKJKxAx
User-Agent: G2/1.0
X-HTTP-UserAgent: Mozilla/5.0 (X11; U; Linux x86_64; en-US) AppleWebKit/534.3 (KHTML,
like Gecko) Ubuntu/10.04 Chromium/6.0.472.36 Chrome/6.0.472.36
Safari/534.3,gzip(gfe)
Xref: news-archive.icm.edu.pl pl.comp.programming:186595
[ ukryj nagłówki ]
On Aug 19, 3:35 pm, Mariusz Marszałkowski <m...@g...com> wrote:

> Wyobraźmy sobie przykładowy program S:
> Pod zerowym adresem jest miejsce na odpowiedź.
> Począwszy od pierwszego adresu do adresu NS są instrukcje
> i dane programu S. Od adresu NS+1 do adresu NP są
> instrukcje programu P, od adresu NP+1 do adresu ND są
> dane programu D. Można napisać:
> S = 0 | INST_S | INST_P | DATA_D [1]

Program P nie jest częścią programu S. Program S dostaje treść
programu P jako swoje dane, ale te dane nie wchodzą w skład programu
S.

> Przy pomocy programu S można napisać program T. Program T
> rozpoznaje czy program S dla programu P i danych D=P programu
> P, zwrócił TAK czy NIE. Jeśli program S zwrócił TAK, to program
> T wpada w wieczną pętlę, jeśli program S zwrócił NIE, to program
> T kończy swoje działanie.
>
> Wyobraźmy sobie program T w pamięci:
> T = INST_T | S = INST_T | 0 | INST_S | P | P [2]

Również tutaj treść P nie jest częścią T, tylko danymi dla T. Zatem
T(T) nie ma dodatkowej kopii danych dla T.